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. 




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.


Example 2:


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. 



Example 3:


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 L = anbn


Same way if this production A → aabbAab | λ is recursively calling so, we will derive (aabb)n(ab)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: