Question

Consider the following CFG:

$\begin{array}{l}\mathbf{S}\mathbf{\to }\mathbf{S}\mathbf{S}\mathbf{|}\mathbf{T}\\ \mathbf{T}\mathbf{\to }\mathbf{a}\mathbf{T}\mathbf{b}\mathbf{|}\mathbf{a}\mathbf{b}\end{array}$

Describe $\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$and show that G is ambiguous. Give an unambiguous grammar$\mathbf{\left(}\mathbf{H}\mathbf{\right)}$ where $\mathit{L}\mathbf{\left(}\mathbf{H}\mathbf{\right)}\mathbf{=}\mathit{L}\mathbf{\left(}\mathbf{G}\mathbf{\right)}$and sketch a proof that $\mathbf{\left(}\mathbf{H}\mathbf{\right)}$is unambiguous.

Short answer

.

Step-by-step solution

Step 1: Define unambiguous context-free grammar and ambiguous CFGs

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

It means that for all strings of a language, there exist more than one left most derivation or more than one right most derivation or more than one parse tree. This is called ambiguous grammar.

Prove the grammar is ambiguous context-free grammar

$\begin{array}{l}S\to SS|T\\ T\to aTb|ab\end{array}$

The given grammar isambiguous context-free grammar, because the language and the string are formed bythe given context-free grammar; there exist more than one left most derivation or more than one right most derivation or more than one parse tree. This is called ambiguous grammar.

$\begin{array}{l}S\to SS|T\\ T\to aTb|ab\end{array}$

The LHS derivation of the given grammar

$\begin{array}{l}S\to SS|T\\ \begin{array}{l}S\to SS\\ S\to TS\\ S\to aTbS\\ \end{array}\end{array}$

$\begin{array}{l}S\to aTbS\\ S\to aabbS\\ S\to aabbT\\ S\to aabbab\end{array}$

The RHS derivation of the given grammar

$\begin{array}{l}S\to SS|T\\ \begin{array}{l}S\to SS\\ S\to ST\\ S\to Sab\\ \end{array}\end{array}$

$\begin{array}{l}S\to Sab\\ S\to Tab\\ S\to aTbab\\ S\to aabbab\end{array}$

From both the derivations - from LHS andRHS - the evaluation is the same; hence, this grammar is ambiguous context-free grammar.

Step 3: Explainunambiguous context-free grammar

The grammar for the second part of the question is

$S\to aSbS\left|bSaS\right|aS|\in$

{W | the number of ’s is at least the number of ’b s in w }.

The unambiguous CFGs context-free grammar is one 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.

By the given language, it is clear that there the number of ’s is at least the number of b’s in W . This is possible only by the given grammar.

The grammar of that string is shown below.

$S\to aSbS\left|bSaS\right|aS|\in$
$aSbS\left|bSaS\right|$generates equal number of a’s and ’bs.

Hence, this grammar is unambiguous CFGs becauseonly one parse tree or only one derivation tree is possiblefrom thiscontext-free grammar.