GATE 2003
March 19, 2025GATE 2005-IT
March 19, 2025GATE 2003
|
Question 51
|
Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → aSb | SS | ε Which of the following statements is true?
|
G is not ambiguous
|
|
|
There exist x, y ∈ L(G) such that xy ∉ L(G)
|
|
|
There is a deterministic pushdown automaton that accepts L(G)
|
|
|
We can find a deterministic finite state automaton that accepts L(G)
|
Question 51 Explanation:
a) False
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a’s = no’ of b’s. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count ‘a’ for no. of ‘b’.
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a’s = no’ of b’s. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count ‘a’ for no. of ‘b’.
Correct Answer: C
Question 51 Explanation:
a) False
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a’s = no’ of b’s. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count ‘a’ for no. of ‘b’.
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a’s = no’ of b’s. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count ‘a’ for no. of ‘b’.