0
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Apr 24, 2021 at 19:29
  • $\begingroup$ You can't implement that additional constraint with a context-free grammar. $\endgroup$
    – rici
    Apr 24, 2021 at 19:41
  • $\begingroup$ Is there a rather obvious way to do it without a CFG? $\endgroup$ Apr 24, 2021 at 19:43
  • $\begingroup$ Useful: cs.stackexchange.com/questions/139295/…. See the referenced Wikipedia article, too. $\endgroup$
    – rici
    Apr 24, 2021 at 19:47
  • $\begingroup$ 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. $\endgroup$ Apr 24, 2021 at 20:56

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.