New answers tagged pushdown-automata
3
If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.
So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. ...
0
Pushdown automata are nondeterministic. Therefore you need to simulate all possible execution paths. The problem is that since PDAs support $\epsilon$-moves, there could potentially be infinitely many execution paths, and it's not clear whether there's an a priori bound on an accepting computation.
Using CFGs in Chomsky normal form circumvents all these ...
1
The language of palindromes isn't DCFL, see for example this question, which proves this for the closely related language of even length palindromes. Since DCFL are closed under complementation, it follows that your language is not DCFL.
2
Simple answer: yes, that is allowed. In the example you give, it's simple--depending on the input symbol and the stack contents, there's one and only one choice for the action of the machine in state $q_0$. It's even possible to have several actions as consequence to a single (input, stack top) pair, like this,
-- input 0 and stack top 1, push 0 and go to ...
0
proving kleene closure of DCFL is not DCFL
0
You don't need to remove $F$ from your definition, you just don't use it in the definition for the accepted words.
Let $(p, w, \beta) \in Q \times \Sigma^* \times\Gamma^*$ be the current full state description of the PDA, where $p$ is the current state, $w$ the yet unread input and $\beta$ the current stack. The accepted language $L(M)$ then is normally ...
Top 50 recent answers are included
