Which of the following statements is/are TRUE ? (a) The grammar π‘†β†’π‘†π‘†βˆ£π‘Ž is…

2017

Which of the following statements is/are TRUE ?

(a) The grammarΒ π‘†β†’π‘†π‘†βˆ£π‘ŽΒ Β is ambiguous. (Where 𝑆 is the start symbol)

(b) The grammar 𝑆→0𝑆1∣01π‘†βˆ£πœ–Β Β is ambiguous. (The special symbolΒ πœ–Β represents the empty string) Β (Where 𝑆 is the start symbol)

(c) The grammar (Where 𝑆 is the start symbol)

S -> T/U

T -> x S y | xy | Ο΅

U -> yT

generates a language consisting of the string 𝑦π‘₯π‘₯𝑦𝑦.

  1. A.

    Only (a) and (b) are TRUE.

  2. B.

    Only (a) and (c) are TRUE.

  3. C.

    Only (b) and (c) are TRUE.

  4. D.

    All of (a), (b) and (c) are TRUE.

Attempted by 73 students.

Show answer & explanation

Correct answer: D

Answer: All three statements are true.

  • (a) The grammar S β†’ SS | a is ambiguous.

    Reason: Different parse trees can give the same terminal string. Example for the string "aaa":

    1. Derivation 1 (grouping as ((a a) a)): S β†’ SS β†’ SS S β†’ a S S β†’ a a S β†’ a a a

    2. Derivation 2 (grouping as (a (a a))): S β†’ SS β†’ S SS β†’ S a S β†’ a a S β†’ a a a

  • (b) The grammar S β†’ 0 S 1 | 01 S | Ξ΅ is ambiguous.

    Reason: A single terminal string can have two different derivations. Example for the string "01":

    1. Using the production 01 S: S β†’ 01 S β†’ 01 (with S β†’ Ξ΅)

    2. Using the production 0 S 1: S β†’ 0 S 1 β†’ 0 Ξ΅ 1 = 01 (with S β†’ Ξ΅)

  • (c) The grammar with productions S β†’ T | U, T β†’ x S y | x y | Ξ΅, and U β†’ y T does generate the string y x x y y.

    Reason: Provide a concrete derivation showing the string is in the language:

    1. S β†’ U

    2. U β†’ y T, so S β†’ y T

    3. T β†’ x S y, so S β†’ y x S y

    4. Inner S β†’ T and T β†’ x y, so S β†’ y x (x y) y = y x x y y

    Thus the string yxxyy is derivable; the statement only asserts membership (not uniqueness), so it is true.

Explore the full course: Mppsc Assistant Professor