1
$\begingroup$

I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$

This last one is quite easy to get ($S\to aSb | Sb | b$), but still I am unsure on how to proceed.

I expect to manipulate the language by differentiating cases, and for example I found that if $n>m$, I will have to solve $a^{m+k}b^mc^rd^s, k\ge1$, and if $n<m$, I will have to solve $a^nb^{n+k}c^rd^s, k\ge1$, but, still I don't see the recursivity.

$\endgroup$
1
$\begingroup$

Any word $w$ in $L$ can be split into two words $w$ and $w'$ such that $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$, $w' \in \{c^r d^s \mid r+s > 0\}$ and if the last symbol of $w$ exists and is $d$, then the first symbol of $w$ is $d$. On the other hand, every choice of $w$ and $w'$ that satisfies the above constrains induces a word $w w' \in L$.

In the following grammar the first two productions take care of generating $w'$, while the other productions generate $w$. In particular the nonterminal $X_\alpha^\beta$ with $\alpha \in \{a,b\}$ and $\beta \in \{cd\}$ will generate all the words in $w \in \{a^n b^m c^r d^s \mid n + m = r+ s \}$ such that (i) if $\alpha=b$: then $n=0$ and (ii) if $\beta=c$ then $s=0$.

$$ \begin{align*} S &\to Sd \mid X_a^dd \mid Yc \mid X_a^cc \\ Y &\to Yc \mid X_a^cc \\ X_a^d &\to aX_a^d d \mid X_a^c \mid X_b^d \\ X_a^c & \to aX_a^cc \mid X_b^c \\ X_b^d &\to b X_b^d d \mid X_b^c \\ X_b^c &\to bX_b^cc \mid \varepsilon \end{align*} $$

$\endgroup$
1
  • $\begingroup$ Understood, that was a bit more complex than what I expected! Thanks! $\endgroup$ – Lightsong Jan 16 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.