The two grammars given below generate a language over the alphabet {x, y, z}…
2007
The two grammars given below generate a language over the alphabet {x, y, z}
Which one of the following choices describes the properties satisfied by the strings in these languages?
- A.
G1 : No y appears before any x
G2 : Every x is followed by at least one y - B.
G1 : No y appears before any x
G2 : No x appears before any y - C.
G1 : No y appears after any x
G2 : Every x is followed by at least one y - D.
G1 : No y appears after any x
G2 : Every y is followed by at least one x
Attempted by 13 students.
Show answer & explanation
Correct answer: A
G1 generates strings where x and z can appear before y, but no y appears before any x because the production S → x | zS | yB forces all y's to come after any initial x or z. For G2, the production S → y | zS | xB ensures that every x is followed by at least one y, as B → y | yS forces a y to follow any x. This matches option A exactly, where G1 satisfies 'No y appears before any x' and G2 satisfies 'Every x is followed by at least one y'.
A video solution is available for this question — log in and enroll to watch it.