DSSSB PGT 2021
February 27, 2025Artificial-Intelligence
February 27, 2025Theory-of-Computation
|
Question 2
|
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {⊥, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or , X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack.
Which one of the following options correctly describes the language accepted by P?
Which one of the following options correctly describes the language accepted by P?
|
{ambn | 1 <= m and n<m}
</m}
|
|
|
{ambn | 0 ≤ n ≤ m}
|
|
|
{ambn | 0 <= m and 0 <= n}
|
|
|
{am | 0 <= m}∪{bn | 0 ≤ n}
|
Correct Answer: A
