The Gateway to Computer Science Excellence
0 votes

Let P be a non-deterministic pushdown automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be S. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack.

Which of the following statement is TRUE?

  1. L(P) is necessarily ∑* but N(P) is not necessarily ∑*

  2. N(P) is necessarily ∑* but L(P) is not necessarily ∑*

  3. Both L(P) and N(P) is necessarily ∑*

  4. Neither L(P) nor N(P) are necessarily ∑*

in Theory of Computation by (107 points) | 23 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,274 answers
104,800 users