# Questions tagged [pushdown-automata]

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

422 questions
Filter by
Sorted by
Tagged with
31k 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 ...
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 ...
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 ...
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 ...
9k views

302 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}$...
5k 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?
744 views

11k 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 ...
219 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 ...
17k 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 ...
848 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 ...
1k 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 ...
942 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 ...
4k 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 ...
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 ... 1answer 3k 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 ... 1answer 464 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 ... 1answer 15k 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, ... 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 ... 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 ... 1answer 314 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 ... 1answer 700 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:... 1answer 462 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 ... 1answer 530 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 ... 2answers 475 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... 3answers 1k 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 ... 3answers 89 views ### \mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ k even} \}  is context free language Let \mathcal{L} be context free language over alphabet \Sigma. Define \mathcal{G} as$$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ ...
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 \$...