...
Question 7977 – GATE 2017 [Set-2]
November 16, 2023
Question 14237 – Set-Theory
November 16, 2023
Question 7977 – GATE 2017 [Set-2]
November 16, 2023
Question 14237 – 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}
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!