Question

Give unambiguous CFGs for the following languages.

a. {$\mathbf{w}$ | in every prefix of w the number of a’s is at least the number of b’s}

b. {$\mathbf{w}$ | the number of a’s and the number of b’s in w are equal}

c. { $\mathbf{w}$| the number of a’s is at least the number of b’s in w}?

Short answer

a. The grammar of that string is $\mathrm{S}\to \left(\mathrm{S}\right)\mathrm{S}\left|\left(\mathrm{S}\right)\right|\in$

{$\mathrm{w}$ | in every prefix of $\mathrm{w}$ the number of $a$’s is at least the number of $\mathrm{b}$’s}

b).The grammar of that string is, $\mathrm{S}\to \mathrm{aSbS}\left|\mathrm{bSaS}\right|\in$.

{$\mathrm{w}$| the number of$\mathrm{a}$’s and the number of$\mathrm{b}$’s inare equal}

c).The grammar of that string is, $\mathrm{S}\to \mathrm{aSbS}\left|\mathrm{bSaS}\right|\mathrm{aS}|\in$ .
{ $\mathrm{w}$| the number of $a$’s is at least the number of $b$’s in $\mathrm{w}$}

Step-by-step solution

Step 1: Unambiguous context free grammar.

The unambiguous CFGs context free grammar is a context free grammar by which only one parse tree or only one derivation tree is possible.

The unambiguous context free grammar (CFGs) for the given language.

a).

{$\mathrm{w}$| in every prefix of $\mathrm{w}$ the number of $\mathrm{a}$’s is at least the number of $\mathrm{b}$’s}

Replace $"\mathrm{a}"$ with open bracket and $\mathrm{b}$ with closing bracket. Then the big picture that to talking about set of prefixes of balanced parenthesis language.

for finding the ambiguity free context free grammar is not that trivial.

first step to find an unambiguous grammar is finding a grammar, unambiguous or ambiguous.

Secondly, if there is ambiguity in it then explore it to know it deeper. And set a priority rules set which will tell you which of the parse tree (derivation) which have to pick. And now set production rules.

$\mathrm{S}\to \mathrm{SS}\left|\left(\mathrm{S}\right)\right|\in$

but it is ambiguous. Then evaluate next grammar by the language given in the equation.

$\mathrm{S}\to \left(\mathrm{S}\right)\mathrm{S}|\in$

The grammar of that string is shown below:

{$\mathrm{w}$ | in every prefix of $\mathrm{w}$ the number of $\mathrm{a}$’s is at least the number of $\mathrm{b}$’s}

$\mathrm{S}\to \left(\mathrm{S}\right)\mathrm{S}\left|\left(\mathrm{S}\right)\right|\in$

Step 3: Unambiguous CFGs for the given language.

b).

{$\mathrm{w}$| the number of$\mathrm{a}$’s and the number of$\mathrm{b}$’s in$w$are equal}, For evaluating the context free grammar for this language, it must be accepted by the pushdown deterministic automata. And The unambiguous CFGs context free grammar is a context free grammar by which only one parse tree or only one derivation tree is possible.

So, here the number of$\mathrm{a}$’s and the number of$\mathrm{b}$’s in$\mathrm{w}$are must be equal, this is only possible by the given grammar.

The grammar of that string is shown below:

$\mathrm{S}\to \mathrm{aSbS}\left|\mathrm{bSaS}\right|\in$.

Step 4: The unambiguous CFGs for the given language.

c).

The given grammar is {$\mathrm{w}$| the number of$\mathrm{a}$’s is at least the number of$\mathrm{b}$’s in$\mathrm{w}$}. And The unambiguous CFGs context free grammar is a context free grammar by which only one parse tree or only one derivation tree is possible.

For evaluating the context free grammar for this language, it must be accepted by the pushdown deterministic automata.

And by the given language it is clear that there the number of$\mathrm{a}$’s is at least the number of$\mathrm{b}$’s in $\mathrm{w}$. This is possible only by the given grammar.

The grammar of that string is shown below:

$\mathrm{S}\to \mathrm{aSbS}\left|\mathrm{bSaS}\right|\mathrm{aS}|\in$

$\mathrm{aSbS}\left|\mathrm{bSaS}\right|$ generates equal number of $\mathrm{a}$ and $\mathrm{b}$.