DHARM330 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEBut for the case of CFLs there is no answer of this question. Why? Because for the CFGs
G 1 and G 2 this problem says,
Is L(G 1 ) = L(G 2 )?
Or, to evaluate the function
Yes
Equiv_cfg(G 1 , G 2 )
No
Algorithm never exists.
l Problem of Ambiguity
Given a CFG G, Is G ambiguous? Or,
For a given CFL L, Is L ambiguous?
Algorithm never exists.
l Problem of Intersection
Given two CFGs G 1 and G 2 , Is there intersection L(G 1 ) ∩ L(G 2 ) is also CFL?
To decide whether there intersection returns a CFL, no algorithm exists.
l Problem of Complementation
Given a CFG G, then what’s about the complement of its language?
Is L(G) is CFL?
Algorithm never exists.
l Problem of equivalence of languages of ambiguous and unambiguous CFG
Given an ambiguous CFG G, Does there exist an equivalent unambiguous CFG G′ s.t. L (G) =
L(G′)?
No algorithm exists.
l Problem of regularity
Given a CFL L, Is L regular?
There is no way to find that L is also a regular language.
EXERCISES
11.1 Classify the grammar and construct the language generated by them
(i)S → aSBC/abC(ii)S → 0A0
bB → bb A → 0A0/1
bC → bc
CB → BC
cC → cc
(iii)S → 0S/0B
B → 1C
C → 0C/0