Build a Context-Free Grammar for a given language

3.4k Views Asked by At

$L_1 = \{a^n b^m a\mid n\geqslant1,m\geqslant0\} $

I can't really seem to figure the list of productions for this simple language, I know I have to write the non-terminals, but how do I decide which is the starting point S? And then how do I continue?

1

There are 1 best solutions below

5
On

!!Answer to the original question for $L= \{a^n b^n a | n\geq1, m\geq0\}$!!

The starting point is some non-terminal symbol you define as such, let us call it S.

Now we observe that the numbers of a and b in $a^n b^n$ must be equal. The obvious way to achieve this is to generate them in pairs. Because we do not want them mixed, the non-terminal must be inbetween them: $A \rightarrow aAb$.

To generate the final $a$ we use $S\rightarrow Aa$.

For terminating $A \rightarrow ab$.