Discussion
Consider the pushdown automaton (PDA) \(P\) below, which runs on the input alphabet \(\{a, b\}\), has stack alphabet \(\{\bot, 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/\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 \(\bot\) in it. The PDA accepts by empty stack.
Which one of the following options correctly describes the language accepted by \(P\)?
Answer: A
The language is \(\{a^{m}b^{n} \mid 1 \le m \text{ and } n \lt m\}\).
In state s each a pushes an A, so after \(a^{m}\) the stack holds m A's above \(\bot\). Each b in state p pops one A. To empty the stack the PDA must reach q, where it can pop all remaining A's and finally \(\bot\). But both moves into q, from s or from p, need an A on top of the stack.
- With no a's (m = 0) the top is \(\bot\) and q is unreachable, so \(m \ge 1\).
- After n b's, \(m - n\) A's remain; moving to q needs at least one, so \(n \lt m\). With n = m the stack shows \(\bot\) in p and the PDA is stuck.
\(0 \le n \le m\) wrongly allows n = m and m = 0, the empty string included. \(0 \le m, 0 \le n\) has no relation between the counts at all. Strings of b's alone cannot be accepted, since b needs an A to pop, which rules out the last option.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development