Question

Give a context-free grammar that generates the language

$\mathit{A}\mathbf{=}\left\{a^i{b}^j{k}^k\overline{)i=j}orj=kwherei,j,k\ge 0\right\}$

Is your grammar ambiguous? Why or Why not?

Short answer

Context-free grammar:

$\begin{array}{rcl}S& \to & T_{ab}C\overline{)A{T}_{bc}}\\ T_{ab}& \to & a{T}_{ab}b\overline{)\epsilon }\\ T_{bc}& \to & b{T}_{bc}c\overline{)\epsilon }\\ C& \to & Cc\overline{)\epsilon }\\ A& \to & Aa\overline{)\epsilon }\end{array}$

The grammar is ambiguous, because a string can be derived in more than one way.

Step-by-step solution

Explain context-free grammar

Context-free grammar is the set of rules that are used to recognize the context-free language. The context-free grammar contains the production rules, variables, and terminals.

Provide example of context-free grammar

Consider the given language

$A=\left\{a^i{b}^j{c}^k\overline{)i=j}orj=kwherei,j,k\ge 0\right\}$, The context-free grammar for the given language can be derived as follows:

$\begin{array}{rcl}S& \to & T_{ab}C\overline{)A{T}_{bc}}\\ T_{ab}& \to & a{T}_{ab}b\overline{)\epsilon }\\ T_{bc}& \to & b{T}_{bc}c\overline{)\epsilon }\\ C& \to & Cc\overline{)\epsilon }\\ A& \to & Aa\overline{)\epsilon }\end{array}$

Consider the string $\epsilon$ ; it can be derived in more than one way. By choosing the T_abC , and substituting T_ab by $\epsilon$ , C by $\epsilon$ . In other way, AT_bc can be chosen, and substituting A by $\epsilon$, T_bc by $\epsilon$.

Therefore, the grammar is ambiguous, because a string can be derived in more than one way.