Computer Sciences > GATE 2023 > Theory of Computation
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 e, 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?
A
{ambn | 1 ≤ m and n < m}
B
{ambn | 0 ≤ n ≤ m}
C
{ambn | 0 ≤ m and 0 ≤ n}
D
{am | 0 ≤ m} ∪ {bn | 0 ≤ n}

Correct : b

Similar Questions

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s,p,q,r}, with s being th...
#952 MCQ
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: Which one of the fo...
#956 MCQ
Consider the context-free grammar G below: S -> aSb | X X -> aX | Xb | a | b where S and X are non-terminals, and a and b are terminal symbols. The starting non...
#974 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......