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

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$$?

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$$

• Thank you very much! It's clear now. However, now I am battling with a constraint added to the problem: $L = \{a^n b^n c^m d^m \mid n \geq 1, m \geq 0, n > m\}$. I've been trying for the last two hours to include the constraint $n > m$. Now, everytime we add a $c/d$ we need to add at least one more $a/b$ but I can't recognize how we could recursively build up this string. Apr 24 '21 at 19:29
• You can't implement that additional constraint with a context-free grammar.
– rici
Apr 24 '21 at 19:41
• Is there a rather obvious way to do it without a CFG? Apr 24 '21 at 19:43
• Useful: cs.stackexchange.com/questions/139295/…. See the referenced Wikipedia article, too.
– rici
Apr 24 '21 at 19:47
• I see. So I have to generate symbols in a specific way and then use a reordering trick (rule) to ensure we generate a pair of a/b for every pair of c/d at least. Apr 24 '21 at 20:56