Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

Question

I'm trying to understand how the construction of simple grammars works.

In my textbook, there's the following example I am supposed to find a grammar for:

Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$. Find a grammar $G = (\Sigma, N, S, P)$ - where $N$ denotes the non-terminals, $S$ the start symbol and $P$ the production rules - such that $L(G) = L_1$, i.e. the grammar $G$ generates the language $L_1$.

These were my first thoughts analyzing the problem:

• We need to have the same number of $a$'s and $b$'s
• We need to have the same number of $c$'s and $d$'s
• There needs to be at least one $a$ and one $b$
• Examples of such a string: $aabbcccddd$, $ab$, $aabbcd$

Furthermore, let $\lambda$ be the empty symbol.

The start symbol $S$ should map to something like: $$ S \rightarrow XY$$

Then $$X \rightarrow aZb, \; Z \rightarrow X | \lambda$$ $$Y \rightarrow cYd | \lambda$$

Would something like that work? I'm confused because the textbook presented similar grammars and the production rules almost never used the empty symbol ($\lambda$).

Is it possible to construct this grammar without using $\lambda$?

Answer 1

You can always write a grammar without $\lambda$, unless the language itself includes $\lambda$. In that case, you will need the single production $S\to\lambda$ (where $S$ is the start symbol).

There's a simple algorithm for removing $\lambda$ from grammars. First, figure out which non-terminals might produce $\lambda$. (These non-terminals are called "nullable non-terminals".) Then, for each nullable non-terminal and for each production in which it occurs, add a new production which is the same but without the non-terminal. (If the non-terminal appears more than once in the same production, do this for each occurrence of the non-terminal.) Keep doing this until no more additions are possible. Then remove all of the productions with empty right-hand sides, except the empty production for the start symbol (if there is one).

Applying this algorithm to your example, we first find that $Y$ and $Z$ are nullable, while $S$ and $X$ are not. So then we need to add additional productions:

• From $X\to a Z b$, add $X\to a b$.
• From $Y\to c Y d$, add $Y\to c d$.
• From $S\to X Y$, add $S\to X$.

That gives us:

$$S\to X Y, S\to X\\ X\to a Z b, X\to a b \\ Z\to X, Z\to \lambda \\ Y\to c Y d, Y\to c d, Y\to \lambda $$ We then delete the two empty productions, leaving: $$S\to X Y, S\to X\\ X\to a Z b, X\to a b \\ Z\to X \\ Y\to c Y d, Y\to c d $$ At this point, we might note that $Z$ is totally redundant. We can simplify the grammar by just substituting its right-hand side in the only place where it is used: $$S\to X Y, S\to X\\ X\to a X b, X\to a b \\ Y\to c Y d, Y\to c d $$