FOR FREE YEAR SOLVED

Constructing CFL from CFG:

Prerequisite: Identify Language from grammar

How write Context Free Language for Context Free Grammar:

We already discuss how to derive a language from a certain grammar in chapter Identify Language from grammar.

In this chapter we only a few construct Context Free Language from Context Free Grammar. 

Example1:

Consider a CFG: S → xSy | z. 

Answer:

To derive the language from this given CFG we can take iteration of x & y upto any number of time and stop it by production S → z. 

If we take n iteration then we will drive the language.

Example 2:

Consider a CFG: S → xS | Sy | z. Drive the corresponding language.

Answer:

As we know this production S → xS | Sy  derive (x + y)*. And we can stop it by production S → z. 

Example 3:

Consider a CFG:

Derive the corresponding language. the ,

Answer:

In that case, we replace variable or non-terminal by its production. Here we replace ‘B’ on the production A → aaBb | λ. 

Now this production A → aabbAab | λ is look like a production A → aAb | λ and we know this type of production gives $\mathbf{L}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}$. 

Same way if this production A → aabbAab | λ is recursively calling so, we will derive ${\mathbf{\left(}\mathbf{aabb}\mathbf{\right)}}^{\mathbf{n}}{\mathbf{\left(}\mathbf{ab}\mathbf{\right)}}^{\mathbf{n}}$.

Now we put the value of A at the production of B:

Finally, we replace B at the production of S:

So, the final language of this given grammar: