Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
539
questions
51
votes
2
answers
46k
views
Is a push-down automaton with two stacks equivalent to a turing machine?
In this answer it is mentioned
A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
- 1,077
40
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.8k
26
votes
3
answers
2k
views
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$
As pointed out by sdcvvc, a word in this language can also be ...
- 747
24
votes
1
answer
4k
views
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)
There may also exist a Deterministic Pushdown ...
- 709
17
votes
1
answer
11k
views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
- 305
17
votes
1
answer
6k
views
Is it decidable whether a pushdown automaton recognizes a given regular language?
The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable ...
- 5,382
15
votes
4
answers
1k
views
Push Down Automatons "guess" - what does that mean?
I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
- 253
14
votes
2
answers
3k
views
Does the language of Regular Expressions need a push down automata to parse it?
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
- 893
13
votes
1
answer
394
views
Computing the intersection of two NPDA where it is possible
Apropois to Raphael's suggestion on Intersection of two NPDAs:
Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
- 1,133
12
votes
5
answers
2k
views
is it possible to minimize pushdown automata?
is it possible to minimize pushdown automata?
If no, why?
Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
- 121
11
votes
1
answer
947
views
How to prove that ε-loops are not necessary in PDAs?
In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
- 72k
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
9
votes
2
answers
906
views
Myhill-Nerode style characterization of CFL?
Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$.
The Nerode equivalence ${\sim}_L$ has ...
- 3,452
9
votes
1
answer
3k
views
Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
- 2,932
9
votes
2
answers
3k
views
Decidability of halting problem for DPDAs with $\epsilon$-transitions?
For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.
But what about PDAs with $\...
- 743
9
votes
1
answer
27k
views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
- 227
8
votes
3
answers
6k
views
Why do pushdown automata use a stack?
I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
- 199
8
votes
2
answers
4k
views
How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
I have tried to reduce this problem to another undecidable ...
- 1,587
8
votes
2
answers
343
views
Is {a^n (a+b)^n | n>0} a Deterministic CFL?
$L = \{ a^n (a+b)^n | n>0\}$
A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
- 740
8
votes
1
answer
5k
views
Are DCFLs closed under reversal?
According to this chart, DCFLs are closed under reversal.
However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
- 259
8
votes
1
answer
437
views
Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?
These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
- 29.6k
8
votes
1
answer
4k
views
prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?
Is ...
- 991
8
votes
1
answer
1k
views
Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
- 747
8
votes
3
answers
4k
views
Demonstrate that DPDA is closed under complement by construction
I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
- 317
8
votes
1
answer
330
views
Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$
Clearly, $\text{Deterministic one-counter} \subseteq A$
Is it the case that $ A = \text{Deterministic one-counter}$...
- 1,269
7
votes
2
answers
1k
views
Do NPDA work in parallel?
Assume my language is
$$
L= ww^{r}\
$$
Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
- 431
7
votes
1
answer
801
views
Converting a context free grammar to a PDA -- is my solution correct?
I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:
$\qquad\begin{align}
S &\to R1R1R1 \\
R &\to ...
jfisk
7
votes
1
answer
1k
views
Who first introduced the pushdown automaton?
I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
- 9,037
7
votes
1
answer
2k
views
Removing $\epsilon$ transitions in a NPDA
NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.
However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
- 93
7
votes
3
answers
13k
views
Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$
I'm having a lot of trouble constructing a PDA for the language: \begin{equation*}
\{a^m b^n : m < 2n < 3m \}
\end{equation*}
I know if I push a symbol for each $a$ I see, then pop 2 symbols ...
- 232
6
votes
3
answers
10k
views
Can you pop 2 elements at a time in a PDA
My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously
- 61
6
votes
1
answer
6k
views
Does DPDA accept all regular languages?
A DPDA which accepts by empty stack cannot accept all Regular Languages?
Is it true that the DPDA cannot accept all regular languages?
I am not able to understand this.As per my knowledge DPDA are ...
- 431
6
votes
2
answers
1k
views
Intersection of two NPDAs
Is there a way to take the interection of two NPDAs?
I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
- 1,133
6
votes
1
answer
1k
views
A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
It is known that a PDA with two stacks is equivalent to a TM.
On the other hand a PDA with one stack is capable to recognise only context-free languages.
Hence there is a kind of a gap between the ...
- 345
6
votes
1
answer
826
views
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?
I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
- 381
6
votes
2
answers
3k
views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
- 163
6
votes
1
answer
855
views
Undecidable problem intersection of two DCFL languages is DCFL?
We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
- 201
6
votes
1
answer
2k
views
pda: transformation between acceptance by empty stack and final states
I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
- 63
6
votes
0
answers
315
views
Why does Non Determinism not enhance FA like it does for PDA
Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
- 161
5
votes
6
answers
25k
views
Are Turing machines more powerful than pushdown automata?
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
- 2,193
5
votes
3
answers
3k
views
Context-free grammar of the concatenation of a string S and subsequence of reversed S
I have to find a Context-Free grammar that generates the language:
$L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$
The concatenation of two mutually ...
- 137
5
votes
2
answers
47k
views
How to convert PDA to CFG
I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?
For example: to write CFG for the automata
My attempt:
$S=A_{03}$ because $...
- 449
5
votes
2
answers
17k
views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
- 4,259
5
votes
2
answers
3k
views
When does a PDA halt?
In DFA/NFA the automaton halts when it finishes reading the string.
In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or ...
- 223
5
votes
3
answers
2k
views
Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?
Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$.
Obviously, this class is a ...
5
votes
2
answers
1k
views
How to get 2-state PDA for CFG?
I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
- 51
5
votes
2
answers
5k
views
why are deterministic PDAs not closed under concatenation?
I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this ...
- 1,269
5
votes
1
answer
6k
views
How does a two-way pushdown automaton work?
Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.
I recently had the question of determining the computational power ...
- 435
5
votes
1
answer
936
views
Why can PDAs only write one symbol to the stack according to this definition?
This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser.
The transition is defined as
$$
\delta: Q\times \Sigma_\varepsilon \times ...
- 175
5
votes
1
answer
5k
views
Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
- 349