Given G, a phrase-structure grammar. Let G = (V, T, S, P), where V = {a, b, A, B

Question

Given G, a phrase-structure grammar. Let G = (V, T, S, P), where V = {a, b, A, B, S}, T = {a, b}, S is the start symbol. P = {S rightarrow AbBa, A rightarrow BB, Ab rightarrow aA, B rightarrow aba, AB rightarrow b}. What is the language generated by G, L(G), that is the set of all strings of terminals that are derivable from the starting state S. Select one: a. {'01011010', ?11010', 010', '00101010', '011100'} b. {Ababa, BBbaba, Babbaba, ababbaba, aABa, aba, aABa, aBBBa, aabababa} c. {ababbaba, aba, aabababa} d. {abaabababaa, aba, aabaabaabaa} e. {aabbaba, ababbaba, aba, aabababa}

Explanation / Answer

The correct answer is Option D

Reason: The starting letter is of the form AbBa, the B must be matched to the smaller "aba" and there is no matching for small a

Hence the end string of the language must be form aba

The only answer which contrains that string is Option D, hence correct answer is Option D

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.