39
votes
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 ...
- 71.9k
28
votes
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 ...
- 5,349
16
votes
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 ...
- 5,349
15
votes
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 ...
- 3,562
11
votes
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$ ...
- 7,365
9
votes
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 ...
- 274k
9
votes
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 ...
- 274k
8
votes
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 ...
- 274k
8
votes
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 ...
- 29.6k
8
votes
Accepted
Does DPDA accept all regular languages?
It is the property "accepting by empty stack" what makes the DPDA weaker. If a language $L$ is accepted by a DPDA by empty stack, then $L$ has the prefix property. The following language $L = \{ b^n \...
- 9,727
8
votes
Accepted
Why equality is decidable for regular language but not for $CFL?$
The short (and not very useful) answer is that we can prove that PDA equivalence is undecidable, and we can prove that DFA equivalence is decidable.
It is important to realize that formally, the above ...
- 17k
8
votes
Accepted
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
If two strings $w_1, w_2$ of the same length are different from each other, then you can find a specific position where they differ:
$$w_1 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\...
- 758
8
votes
Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form
Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.
D.W.♦
- 154k
7
votes
Accepted
How to convert PDA to CFG
There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals.
Added, as ...
- 13.9k
7
votes
Can you pop 2 elements at a time in a PDA
In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and ...
- 274k
7
votes
Accepted
Does a PDA immediately accept if at final state with empty stack?
There are two ways in which a PDA may accept:
Final state: The PDA has finished reading the input and it is in the final state
Empty stack: The PDA has finished reading the input and its stack is ...
- 204
7
votes
Do NPDA work in parallel?
That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism.
The genie. Whenever the machine has a choice, a ...
- 274k
7
votes
Accepted
Do NPDA work in parallel?
The difference between DPDA and NPDA is that in NPDA there may be more than one possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one ...
- 9,727
7
votes
Accepted
Context-free grammar of the concatenation of a string S and subsequence of reversed S
Let me start with a grammar for the language of words of the form $x\#x^R$:
$$
S \to aSa \mid bSb \mid \#
$$
This is our starting point. Now there are two interpretations of the term subsequence. ...
- 274k
7
votes
Accepted
Are 2 independent PDAs equivalent to a turing machine?
No, such a construct can recognise at most the intersection of two context-free languages. To see where it's lacking, consider $L = \{\textsf{a}^n~|~n\in\mathbb{N}~\text{is composite}\}$. I conjecture ...
- 614
6
votes
Accepted
Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
Yes, deterministic context-free languages are closed under union with regular languages.
It is easy to show they are closed under intersection with regular languages. We can apply a product ...
- 29.6k
6
votes
Accepted
Why can PDAs only write one symbol to the stack according to this definition?
The addition of $\epsilon$ to the alphabets allows the pop and push operations. For example, if you want to push the letter $a$ in state $q$, without reading anything from the input, you can have the ...
- 17k
6
votes
Accepted
Is $L / R$ context free?
You can't prove a general theorem by proving one special case. So even if your proof of the special case were correct (and it isn't), all it does is prove that the theorem holds in that specific case.
...
- 274k
6
votes
Why are DCFL not closed under concatenation or Union whereas CFL is?
The fact that is a proper subset does not inherit the global properties in general is common in mathematics and computer science. A proper subset does not have to inherit the global properties of its ...
- 9,727
6
votes
Accepted
Are all finitely recursive context free languages parseable with a regexp?
We can take it even further: if we put a limit on the size of the HTML/XML, say 1PB, then there is only a finite number of them, so we can trivially parse them in $O(1)$ using a giant look-up table. ...
- 274k
6
votes
Accepted
A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.
What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick ...
- 12.4k
6
votes
Accepted
Does this argument prove CFLs are not closed under union?
Your first proof is valid. You are assuming by contradiction that CFLs are closed under complement and arriving at the absurd conclusion that they must be closed under intersection. Notice that this ...
- 27.4k
6
votes
Are 2 independent PDAs equivalent to a turing machine?
What you actually ask is: can language of every grammar be represented as an intersection of two context-free languages?
The answer is no.
To prove that, we can observe that, while the class of ...
- 161
5
votes
Accepted
Removing $\epsilon$ transitions in a NPDA
This effect I would not consider this a "halting problem" but there is a point here. A pushdown automaton can end its computation in an unbounded sequence of $\varepsilon$-moves. This behaviour can be ...
- 29.6k
5
votes
Accepted
Deterministic vs. Non-Deterministic PDA?
Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.
Your example is ...
- 13.9k
Only top scored, non community-wiki answers of a minimum length are eligible