Web-Technologies
November 27, 2023Web-Technologies
November 27, 2023UGC-NET DEC-2019 Part-2
| Question 6 |
L1 = {anbncm} ∪ {an bm cm}, n. m ≥ o
L2 = {ωωR |ω ∈ {a, b}*} Where R represents reversible operation.
Which one of the following is (are) inherently ambiguous language(s)?
| only L1 | |
| only L2 | |
| both L1 and L2 | |
| neither L1 nor L2 |
If for a language every existing grammar is ambiguous then that language is called inherently ambiguous language. By this definition of inherently ambiguous, we can conclude that for an inherently ambiguous language an equivalent unambiguous grammar can’t be found.
There are several languages (special types ) which are inherently ambiguous.
For example : L= {ai bj ck | i=j or c=k} is inherently ambiguous
The reason is : It is union of two languages
{an bn cm} U {an bm cm}
So it will have grammar
S-> A | B
A-> PQ
P->aPb | ab
Q-> cQ | c
B-> UV
U-> aU | a
V-> bVc | bc
Grammar A generates equal number of a’s and b’s and any number of c’s
Grammar B generates equal number of b’s and c’s and any number of a’s
So the strings which have equal numbers of a’s, b’s and c’s can be generated by A or B
So for these strings we always have two parse trees.
Hence this language is ambiguous as we cannot make an unambiguous grammar for it.
If for a language every existing grammar is ambiguous then that language is called inherently ambiguous language. By this definition of inherently ambiguous, we can conclude that for an inherently ambiguous language an equivalent unambiguous grammar can’t be found.
There are several languages (special types ) which are inherently ambiguous.
For example : L= {ai bj ck | i=j or c=k} is inherently ambiguous
The reason is : It is union of two languages
{an bn cm} U {an bm cm}
So it will have grammar
S-> A | B
A-> PQ
P->aPb | ab
Q-> cQ | c
B-> UV
U-> aU | a
V-> bVc | bc
Grammar A generates equal number of a’s and b’s and any number of c’s
Grammar B generates equal number of b’s and c’s and any number of a’s
So the strings which have equal numbers of a’s, b’s and c’s can be generated by A or B
So for these strings we always have two parse trees.
Hence this language is ambiguous as we cannot make an unambiguous grammar for it.