Question 7977 – GATE 2017 [Set-2]
November 16, 2023
Set-Theory
November 16, 2023
Question 7977 – GATE 2017 [Set-2]
November 16, 2023
Set-Theory
November 16, 2023

Question 7978 – GATE 2017 [Set-2]

Identify the language generated by the following grammar, where S is the start variable.

                                     S → XY
                                     X → aX|a
                                     Y → aYb|ϵ

Correct Answer: C

Question 16 Explanation: 
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.

So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {am bn│m>n,n≥0}.
A
{am bn │ m ≥ n, n > 0}
B
{am bn │ m ≥ n, n ≥ 0}
C
{am bn │ m > n, n ≥ 0}
D
{am bn │ m > n, n > 0}

Leave a Reply

Your email address will not be published. Required fields are marked *