Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

Filter by
Sorted by
Tagged with
40
votes
1answer
27k 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 ...
36
votes
2answers
5k 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 ...
25
votes
3answers
1k 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 ...
21
votes
1answer
2k 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 ...
16
votes
1answer
7k 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 $...
16
votes
1answer
3k 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 ...
14
votes
4answers
587 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 ...
13
votes
1answer
260 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 ...
12
votes
2answers
2k 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 ...
10
votes
1answer
467 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 ...
9
votes
3answers
2k 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-...
9
votes
1answer
1k 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 ...
9
votes
1answer
21k 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 ...
8
votes
5answers
863 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?
8
votes
2answers
2k 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 ...
8
votes
2answers
547 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 ...
8
votes
1answer
3k 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 ...
8
votes
1answer
317 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 ...
8
votes
1answer
535 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 ...
8
votes
3answers
2k 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 ...
8
votes
1answer
274 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}$...
7
votes
3answers
4k 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?
7
votes
2answers
230 views

Is this language a Deterministic CFL? $L = \{ a^n (a+b)^n | n>0\}$

$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 ...
7
votes
1answer
718 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 ...
7
votes
1answer
2k 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 ...
6
votes
1answer
2k 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 $\...
6
votes
2answers
402 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.
6
votes
1answer
220 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 ...
6
votes
0answers
162 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 ...
5
votes
2answers
677 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 ...
5
votes
2answers
855 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 ...
5
votes
2answers
3k 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 ...
5
votes
3answers
950 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
1answer
750 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 ...
5
votes
1answer
302 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 ...
5
votes
1answer
11k views

Deterministic vs. Non-Deterministic PDA?

The following is an example of language $a^nb^n$ where $n \geq 1$ From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, ...
5
votes
2answers
2k 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 ...
5
votes
1answer
675 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 $\...
5
votes
1answer
1k 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 ...
5
votes
1answer
283 views

Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
5
votes
1answer
693 views

Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
5
votes
1answer
501 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
5
votes
2answers
427 views

Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside $L$...
5
votes
3answers
9k 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 ...
4
votes
6answers
14k 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 ...
4
votes
1answer
4k views

Creating a Deterministic Push Down Automata

I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself. ...
4
votes
2answers
6k 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
votes
1answer
3k 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 ...
4
votes
1answer
2k 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 ...
4
votes
1answer
92 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 ...