2
$\begingroup$

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.

In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar for the language of this Context-Free Grammar (where epsilon is the empty string):

$$S \rightarrow aS | aSbS | \epsilon$$

I'm having difficulty describing this grammar formally, but I realize the number of a's is greater than or equal to the number of b's. And the string will always begin with an a (except for the empty string).

I have attempted to break the grammar into two parts to remove the ambiguity. After a few brute force attempts, I decided to distinctly have a variable generate only a's and the other variable generate an equal amount of a's and b's.

$$S \rightarrow A | B | \epsilon$$ $$A \rightarrow aA | a $$ $$B \rightarrow BB | aAbA | ab$$

The key part is when a re-write of B to a sentential form when an A occurs, only more a's can be generated in the string.

My question is does the new grammar I created generate the same language as the previous grammar? If not, what would be the correct grammar? I realize determining if two CFG are equivalent is undecidable; but I have no method of determining if I am correct.

$\endgroup$
  • $\begingroup$ The original grammar generates the language of all words in which in every prefix, there are at least as many $a$s as $b$s. $\endgroup$ – Yuval Filmus Apr 13 at 21:18
  • $\begingroup$ Your grammar is ambiguous: $ababab$ has two different parse trees. $\endgroup$ – Yuval Filmus Apr 13 at 21:19
0
$\begingroup$

First, let us show that the original grammar generates the language $L$ of all words in which in every prefix, there are at least as many $a$s as $b$.

A simple induction shows that every word generated by the grammar satisfies the property. In the other direction, let $w$ be a non-empty word in $L$. We consider two cases:

  1. Some prefix of $w$ has exactly as many $a$s as $b$s. Write $w = axby$, where $axb$ is the shortest prefix with this property. This choice guarantees that $x \in L$. Also, $y \in L$. Hence we can generate $w$ using the rule $S \to aSbS$.

  2. In every prefix of $w$, the number of $a$s exceeds the number of $b$s. Hence $w = az$, where $z \in L$, and we can generate $w$ using the rule $S \to aS$.

Every word $w \in L$ can be written (uniquely) as $w_0 a w_1 a \cdots a w_\ell$, where $w_i$ is a word in $L$ in which the number of $a$s is the same as the number of $b$s. Indeed, $w_0$ is the longest prefix of $w$ in which the number of $a$s is the same as the number of $b$s; $w_0 a w_1$ is the longest prefix of $w$ in which the number of $a$s exceeds the number of $b$s by 1; and so on.

Suppose that $T$ generates unambiguously the language $L'$ of all words in $L$ in which the number of $a$s is the same as the number of $b$s. Then we can generate $L$ itself unambiguously using the productions $S \to T a S \mid T$. The language $L'$ can be generated unambiguously using $T \to aTbT \mid \epsilon$.

$\endgroup$
  • $\begingroup$ I appreciate the thoroughness of your response and the unambiguous grammar provided. I would like to ask, do you have any resources where I can learn heuristics on how to create unambiguous grammars? $\endgroup$ – Denzak Apr 14 at 4:13
  • $\begingroup$ I’m not aware of any, though in a way, literature on yacc or LL grammars should be relevant. $\endgroup$ – Yuval Filmus Apr 14 at 5:02

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.