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 ...
user avatar
  • 70.8k
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 ...
user avatar
  • 4,611
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 ...
user avatar
  • 3,497
14 votes
Accepted

Is it decidable whether a pushdown automaton recognizes a given regular language?

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet. Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-...
user avatar
  • 27.2k
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$ ...
user avatar
  • 7,249
10 votes
Accepted

Are DCFLs closed under reversal?

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter. Searching the web does also give a ...
user avatar
  • 19.1k
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 ...
user avatar
8 votes

Language of binary strings divisible by 7

The langauge is regular, so answers 1–4 are all correct. The (deterministic) automaton has seven states, $0, \dots, 6$ corresponding to the remainder when the number is divided by 7. The ...
user avatar
8 votes

is it possible to minimize pushdown automata?

Unfortunately the problem is not computable. It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.
user avatar
  • 140k
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 ...
user avatar
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 ...
user avatar
  • 27.2k
8 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 ...
user avatar
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 ...
user avatar
  • 16.2k
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\;\...
user avatar
7 votes

is it possible to minimize pushdown automata?

I answered basically the same question (put more generally) here. The argument in short: if you could do this, you could decide universality, and a couple of other undecidable properties of PDA/CFG. ...
user avatar
  • 70.8k
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 ...
user avatar
  • 13.6k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 9,592
7 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 \...
user avatar
  • 9,592
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. ...
user avatar
6 votes
Accepted

Intersection of two NPDAs

The intersection of two context-free languages can be non-context-free. The classical example is $$ \{ a^n b^n c^m : n,m \geq 0 \} \cap \{ a^m b^n c^n : n,m \geq 0 \} = \{ a^n b^n c^n : n \geq 0 \}. $$...
user avatar
6 votes
Accepted

Computing the intersection of two NPDA where it is possible

I think this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet. These correspond to type $\langle 1,1\rangle$ quantifier languages comparing the ...
user avatar
  • 630
6 votes
Accepted

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

If $L_1,L_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L_1 \cup L_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: ...
user avatar
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 ...
user avatar
  • 27.2k
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 ...
user avatar
  • 16.2k
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. ...
user avatar
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 ...
user avatar
  • 9,592
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. ...
user avatar
5 votes

Why Deterministic PDA accepts $\epsilon$ input but DFA not

There are definitely definitions of DFA that allow $\varepsilon$-transitions. Arguably, they are not very useful for three reasons. They don't add computational power. If you have them, you have to ...
user avatar
  • 70.8k

Only top scored, non community-wiki answers of a minimum length are eligible