How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?

181 Views Asked by At

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?

My attempt:

$G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$ S\to AbBC $$ $$A \to aAb|\lambda$$ $$ B \to bB|\lambda $$ $$ C \to bCa|\lambda$$

Is this correct?

1

There are 1 best solutions below

0
On BEST ANSWER

The strings your grammar generate are of the form $\mathtt{a}^i \mathtt{b}^{j} \mathtt{a}^k \mathtt{b}^k$ (or $\mathtt{0}^i \mathtt{1}^{j} \mathtt{0}^k \mathtt{1}^k$ with notational changes) where $j > i$. (You're use of the non-terminal $A$ in two spots in the starting rule made you go awry as the order of the $\mathtt{a}$s and $\mathtt{b}$s (or $\mathtt{0}$s and $\mathtt{1}$s) matters.)

Don't be afraid to use more non-terminal symbols! (well, one more.)