for any language L , the reverse of L , or L R , is thelanguage whose elements a
ID: 3610152 • Letter: F
Question
for any language L , the reverse of L , or LR , is thelanguage whose elements are those elements of L in reverse. For theLanguage L1 = { 0n 1n} ,L1R is { 1n 0n} . The Reverse of the language {dab,toot, mad,unix,reed} is { bad, tot , dam , xinu , deer } .prove that the reverse of a context - free language is also acontext- free language.Explanation / Answer
If the language L is a CFG.....we can write a context freegrammer. Now by reversing the right hand sides of all the rules in the CFGfor L we can get a new CFG..(say L2) Now this L2 gives all the strings which are the reverse of allstrings in L. SO L2 is the reverse language of L.....and we already wrote a CFGfor L2 (by reversing the right hand sides of all rules in L) so L2 has a CFG Therefore reverse of a CFG is also a CFG. Example: Language L1 = { 0n1n} , L1R is { 1n 0n} CFG for L1 is: S --> 0S1 S ---> Now obtain CFG for L2 by reversing the right hand sides ofall rules in L1 there are only two rules in L1 therefore new CFG for L2 is : S --> 1 S 0 S --> [obtained by reversing the right hand sides of rules of L1] Now L2 gives the reverse language of L1.... CFG for L2 is: S --> 1 S 0 S --> Therefore L2 is also a CFG. which means reverse of CFL (L1) is also a CFG
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.