Consider the following context-free grammars: \(G_1 : S \to aS \mid B, B \to b…

GATE · 2016 · CS · Set 1 · Computer Science & IT

Consider the following context-free grammars:

G1:S→aS∣B,B→b∣bBG_1 : S \to aS \mid B, B \to b \mid bB

G2:S→aA∣bB,A→aA∣B∣ε,B→bB∣εG_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon

Which one of the following pairs of languages is generated by G1G_1 and G2G_2, respectively?

  1. A.

    {ambn∣m>0 or n>0}\{ a^mb^n \mid m > 0 \text{ or } n >0\} and {ambn∣m>0 and n>0}\{ a^mb^n \mid m > 0 \text{ and } n >0\}

  2. B.

    {ambn∣m>0 and n>0}\{ a^mb^n \mid m > 0 \text{ and } n >0\} and {ambn∣m>0 or n≥0}\{ a^mb^n \mid m > 0 \text{ or } n\geq0\}

  3. C.

    {ambn∣m≥0 or n>0}\{ a^mb^n \mid m \geq 0 \text{ or } n >0\} and {ambn∣m>0 and n>0}\{ a^mb^n \mid m > 0\text{ and } n>0\}

  4. D.

    {ambn∣m≥0 and n>0}\{ a^mb^n \mid m \geq 0 \text{ and } n >0\} and {ambn∣m>0 or n>0}\{ a^mb^n \mid m > 0 \text{ or } n>0\}

Attempted by 102 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…