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.
Consider a CFG: S → xSy | z.
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.
Consider a CFG: S → xS | Sy | z. Drive the corresponding language.
As we know this production S → xS | Sy derive (x + y)*. And we can stop it by production S → z.
Consider a CFG:
Derive the corresponding language. the ,
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 .
Same way if this production A → aabbAab | λ is recursively calling so, we will derive .
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: