# Tag Info

### Why do pushdown automata use a stack?

There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out ...

### Why do pushdown automata use a stack?

OmG and Raphael have already answered your question: pushdown automata use a stack because they're defined that way if they didn't use a stack, what you'd get is a different type of automaton, with ...
Accepted

### Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Sipser clearly implies an or between those two rules. The two definitions say the same thing. Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same ...
Accepted

### Why do pushdown automata use a stack?

If you change the stack to the queue or multiple stacks, the power of computation will be increased! (as you know, we can model a queue with two stacks). If we use a queue, it can be powerful as a ...
Accepted

### Is {a^n (a+b)^n | n>0} a Deterministic CFL?

You needn't determine the end of "first part". Note $L$ is exactly the set of strings satisfying the following three constraints: Its length is even. It only contains $a$ and $b$. The first $b$ ...
Accepted

### Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always ...

### Why are DCFL not closed under concatenation or Union whereas CFL is?

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily ...
Accepted

### Difference between DPDA and NPDA?

The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of ...
Accepted

### Why DCFL is not closed under kleene star?

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can ...