# 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
37 views

### The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
163 views

### Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
50 views

20 views

### How to create a (N)PDA for L={w∈{a,b}⋆ |w=(a2b)n mitn∈N0}?

I just can't get any further on this task. How should I create a cellar machine for this language? The word is asymmetrical for n = 1 and has a character length of 3. So the cellar will never be empty ...
22 views

### How can I combine 2 PDA's into 1

I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ...
43 views

### Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
31 views

### Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
26 views

### Is there any property about height of PDA?

I'm trying to find a PDA for $L$ which modifies the stack height at most one. $L=\{a^ib^i\mid i\geq 0\}$ I think there is no such PDA but how can I prove it? My attempt is for a given string, find ...
20 views

### Formal definition of non deterministic PDA

How would you convert the following formal definition of deterministic pushdown automata into non deterministic ? Deterministic PDAs In general terms, a deterministic PDA is one in which there is at ...
27 views

### Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
14 views

### Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
11 views

### checking configuration history of Turing machine using PDA

I am trying to understand the technique of using configuration history in proofs. To prove that: $\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$ given $<M,w>$ we ...
135 views

### Prove or disprove {wtw^R | |w| = |t|} is context free

The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$ It looks like the language can be "pumped" by context free pumping lemma, ...
23 views

31 views

### Construct a PDA that recognizes the following language: L={uawb: u,w ∈ {a,b}*, |u|=|w|}

I am having trouble finding the PDA with 1 state for this one. So far my solution is this but i cant figure out how to get to 1 state. Alphabet: {a, b}, Stack alphabet (the first symbol is the ...
22 views

### PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
74 views

### How to convert NPDA to PDA?

I have been given this Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be ...
11 views

### Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]

Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
84 views

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 ... 0answers 79 views ### Question about proof of Lemma 2.41 - Sipser book Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ... 1answer 35 views ### Formal definition of a language accepted by PDA I am a bit confused on how to give a formal definition of the language accepted by A? I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" ... 1answer 80 views ### Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language? In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ... 2answers 74 views ### In a NPDA if the stack is empty, where the start/end state are the same can you go again Thoughts I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ... 1answer 34 views ### PDA for parentheses language Construct a PDA for the language described by the following CFG:$$ S \to [S] \mid \{S\} \mid \Lambda $$How can I develop a pushdown automaton for this language? 1answer 115 views ### How do I convert this PDA to CFG? How do I convert this PDA to CFG? I am currently stuck with this, any help would be appreciated, thank you in advance! 1answer 35 views ### The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ... 1answer 107 views ### Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar? I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ... 2answers 45 views ### Is it decidable for a NPDA to halt? I know that it is decidable for an NPDA to accept a string w, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string. But are there ... 1answer 78 views ### Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack? I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ... 3answers 2k views ### Why DCFL is not closed under kleene star? I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example 0answers 38 views ### How does a PDA compare two configurations of accepting histories? In Michael Sipser's book, they prove that ALL_CFG is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation) a PDA goes on to compare ... 0answers 25 views ### A pda that accepts all strings over an alphabet If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is L={w | w belongs to (a,b,c,d)*} How would that be constructed? My idea is to have one state as ... 1answer 36 views ### How should we interpret a transition rule \epsilon,b\to c in a Pushdown Automata as Sipser defined in his book? After defining pushdown automaton in Sipser's book at p. 113: at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following: My question is about the part "... 1answer 27 views ### Find CFG for the following language I need to show that the following language is context free:$$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}
Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0} I’m trying to design a PDA. My aproach is: -for every 2 ‘a’ push an ‘a’ -for every 4 ‘c’ push a ‘c’ -then pop them ...
Thoughts I am wondering is the language $ab^*$, since $a$ pushes $X$ to the stack and $b$ pops, and if there is an $a$ there has to be a $b$ to get back to the final state? Also, is it right to say \$...