Given the following grammars: 𝐺1π‘†β†’π΄π΅βˆ£π‘Žπ‘Žπ΅π΄β†’π‘Žπ΄βˆ£πœ–π΅β†’π‘π΅βˆ£πœ–πΊ2:π‘†β†’π΄βˆ£π΅β€¦

2015

Given the following grammars:

𝐺1π‘†β†’π΄π΅βˆ£π‘Žπ‘Žπ΅π΄β†’π‘Žπ΄βˆ£πœ–π΅β†’π‘π΅βˆ£πœ–πΊ2:π‘†β†’π΄βˆ£π΅π΄β†’π‘Žπ΄π‘βˆ£π‘Žπ‘π΅β†’π‘Žπ‘π΅βˆ£πœ–

Which of the following is correct ?

  1. A.

    𝐺1 is ambiguous and 𝐺2 is unambiguous grammars

  2. B.

    𝐺1 is unambiguous and 𝐺2 is ambiguous grammars

  3. C.

    both 𝐺1 and 𝐺2 are ambiguous grammars

  4. D.

    both 𝐺1 and 𝐺2 are unambiguous grammars

Attempted by 99 students.

Show answer & explanation

Correct answer: C

Conclusion: Both grammars are ambiguous.

  • First grammar (productions: S β†’ A B | a a B; A β†’ a A | Ξ΅; B β†’ b B | Ξ΅) generates a* b*. It is ambiguous because some strings have two different parse trees. Example: the string "aa".

    1. Derivation 1: S β†’ A B, with A β‡’ a a and B β‡’ Ξ΅, yields "aa".

    2. Derivation 2: S β†’ a a B, with B β‡’ Ξ΅, yields "aa".

  • Second grammar (productions: S β†’ A | B; A β†’ a A b | a b; B β†’ a b B | Ξ΅) generates the union of {a^n b^n | n β‰₯ 1} and (ab)*. It is ambiguous because the string "ab" can be derived in two different ways.

    1. Derivation 1: S β†’ A β†’ a b, yielding "ab".

    2. Derivation 2: S β†’ B β†’ a b B β†’ a b (B β†’ Ξ΅), yielding "ab".

Therefore, because each grammar admits at least one string with two distinct parse trees, both grammars are ambiguous.

Explore the full course: Mppsc Assistant Professor