GATE CS 2023 (Forenoon) — Question 40

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataMCQ2 marks · −2/3 if wrongHard

Consider the pushdown automaton (PDA) \( P \) below, which runs on the input alphabet \( \{a, b\} \), has stack alphabet \( \{\perp, A\} \), and has three states \( \{s, p, q\} \), with \( s \) being the start state. A transition from state \( u \) to state \( v \), labelled \( c \mid X / \gamma \), where \( c \) is an input symbol or \( \epsilon \), \( X \) is a stack symbol, and \( \gamma \) 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 \( \gamma \) on the stack, and go to state \( v \). In the initial configuration, the stack has only the symbol \( \perp \) in it. The PDA accepts by empty stack.
Question image
Which one of the following options correctly describes the language accepted by \( P \)?
  1. A
    \( \{a^m b^n \mid 1 \le m \text{ and } n < m\} \)
  2. B
    \( \{a^m b^n \mid 0 \le n \le m\} \)
  3. C
    \( \{a^m b^n \mid 0 \le m \text{ and } 0 \le n\} \)
  4. D
    \( \{a^m \mid 0 \le m\} \cup \{b^n \mid 0 \le n\} \)
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Context-Free Grammars & Push-Down AutomataTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group