3. Consider a context-free grammar G generating language L and a set D of leftmo
ID: 3725223 • Letter: 3
Question
3. Consider a context-free grammar G generating language L and a set D of leftmost derivations of strings r from L. Observe that a grammar G' generating the set D can be derived from G by modifying the righthand sides of productions; more specifically, by removing all termi nal symbols from the righthand sides and inserting new terminal symbols (the production numbers) in front of the remaining nonterminals. e grammar y' is regular (b) Find a context-free grammar G for which the grammar G' is also context-free.Explanation / Answer
(a) Let G' be a Regular Grammar which generates all string over input alphabets {a,b} which contains only a's. Thus L = {epsilon,a,aa,aaa,aaaa,aaaaa,......}. Thus our Regular language will be of the form:- a*. This can be designed via Finite State Machine. Now we need to design G which is a CFG which will generate the same set of strings as we generated from G'. Thus the Production Rules for G will be:-
S -> | A, A -> aA | Aa | a, where {A,S} = Set of Non Terminals, {a} = Set of Terminals, S - Start Symbol.
(b) Lets us now define a CFG G which has the set of following Production Rules:-
S -> | AB, A -> aA | Aa | a, B -> bB | Bb | b, where {A,B}= set of Non terminals and {a,b} is set of Terminals, S = Start Symbol.
L = {,ab,aab,aabb,abbb,.....} . We can say that these set of strings generated which is accepted by L can ge generated by Leftmost Derievations. eg: S -> AB -> aB -> abB -> abb. Now for this Grammar G', this too is CFG because we can generate all strings from G via Rightmost Derievations which will be accepted by G'.
eg :- S -> AB -> AbB -> Abb -> abb [Rightmost Derievation applied]. Hence in G' we can obtain the same set of strings we have in G.
Please let me know in case of any clarifications required. Thanks!