Context free grammar to language

130 Views Asked by At

Suppose we have $G(V,Σ, R, S)$ where $$\begin{array}{ll} V & = \{a,b,A,B,S\}\\ Σ & = \{a,b\}\\ R &= \left\{ \begin{array}{rl} S &→ abA,\\ S&→B,\\ S&→baB,\\ S&→e,\\ A&→bS,\\ B& →aS,\\ A&→b \end{array}\right\}\end{array}$$

What is language $L(G)$ ? thanks in advance

1

There are 1 best solutions below

0
On

Notice that the only production with $B$ on the left is $B\to aS$, so we can remove that production if we replace every $B$ on the righthand side of a production by $aS$. We then have the following productions:

$$\begin{align*} &S\to abA\mid aS\mid baaS\mid \epsilon\\ &A\to bS\mid b \end{align*}$$

We can repeat the procedure to eliminate the non-terminal symbol $A$:

$$S\to abbS\mid abb\mid aS\mid baaS\mid\epsilon\;.$$

Now it’s easy to see what language is being generated: it’s actually a regular language, which you can describe either in words or by a fairly simple regular expression.