# Questions tagged [pushdown-automata]

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

381 questions
Filter by
Sorted by
Tagged with
122 views

### Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
490 views

### Constructing a turing machine from a PDA - dealing with non-determinism

Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack. But, a PDA transition function may have multiple transitions ...
349 views

### DPDA - a language that contains the same number of A and B

I need help with creating Deterministic pushdown automaton for language: L = {v1w | v, w ∈ {a, b, c}*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string. In the ...
366 views

### Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S [closed]

I am sorta confused and also could not find a answer online, but in terms of expressive power, . Non-deterministic FA, PDA, TM NFA < NPDA < NTM ...
284 views

### Existence of one and two state PDAs

I came across following fact in Automata book by Hopcroft, Ullman: Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack. I was ...
21k views

83 views

### Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
371 views

### Show that 0^n1^n is decidable

I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. ...
110 views

### Push Down automata:- Basic doubt

I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means ...
63 views

### Pushdown automaton for language with “or” [duplicate]

Find a pushdown automaton accepting the language $$L=\{A^i B^j C^k \mid 2k \le i \le 3k \text{ or } j \neq i+k \}.$$ I can't construct the automaton because I can only imagine it with multiple stacks ...
512 views

### Complement of DPDA

I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA. Why can't we do the same with NPDA ? Also is DCFL closed under complement just because we can toggle ...
6k 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
393 views

### Why Acceptance by Final sate and Empty Stack in PDA?

Why there are two ways of accepting the input in PDA i.e. Acceptance by Final sate and Empty Stack I have seen examples which are accepted by both rules? There are some examples which are only ...
769 views

### Working of NPDA

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example ...
86 views

### A push down automaton that recognize exponential strings

How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$? My approach I know that the language can be described by a Turing Machine, but how i can the stack ...
955 views

### How to build a PDA that accepts strings which have odd numbers of a and even numbers of b and has only 2 states?

How can i draw a PDA which has only 2 states and accepts strings which have odd number of a and even number of b? the alphabet is {a,b}, and the PDA has to be only 2 states?
773 views

### Are the sets of all finite automata and pushdown automata countable?

So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering ...
248 views

### is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$ [duplicate]

$L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$ Alphabet = { a , b }* Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a ...
453 views

### Can we make a PDA with only 1 state which accepts a^n and n is odd?

We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong But can we have a non empty ...
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 ...
3k 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 ...
777 views

### Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
751 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 ...
146 views

### Check if given language is CFL

Assume language $L$ as follow:- $$L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\}$$ Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. ...
1k views

### PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
2k views

### simulation of PDA with 2-tape Turing machine [closed]

Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?
346 views

### How to draw NPDA for language $L = \{ a^i b^j c^m \mid m \ge \min( i,j) \}$

$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$ $L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$ Which language is CFL ? ANS : $L_1$ is CFL but $L_2$ is NOT. My understanding :  For Language $L_1$ : ( ...
241 views

### construct a deterministic PDA for the language

Can someone help me to construct a deterministic PDA for the following language: $L = \{0^n1^m | n \geq m$ and $m,n \geq 0 \}$ Here is my suggestion : the states are z0,z1,z2 , z0 is final state ...
67 views

### Providing an algorithm for a given PDA

I was asked the next question in my homework assignment: I just want to make sure that I fully understand what it is that's required of me. Am I asked to find an algorithm which decides if the ...
522 views

### If a language L is regular then the given operation sort(L) is context free

I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it: Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in ...
882 views

### Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)

given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove ...
265 views

### Do deterministic context free grammars always have corresponding deterministic push down automata?

A language $L$ is deterministic context-free if and only if there is a deterministic push-down automaton M such that $L = L(M)$. According to the answer key of this quiz, the above statement is ...
723 views

### Equivalence of final state and empty stack PDA [duplicate]

I have done some reading on these two types of PDA and, to my layman eye, it looks like one simply 'wraps' an empty stack PDA with some extra transitions to create the final state PDA. Since these are ...
781 views

### How do I show that whether a PDA accepts some string w is decidable? or undecidable?

Currently studying for an Automata Theory final and can't find an answer to this question anywhere. Can you simply let w = w!w and show that it is undecidable that way? Like this here: How do I show ...
425 views

### PDA to recognize a language

The PDA has to recognize the language $L = \{w\in \{a,b,c\}^* \mid |w|_a = |w|_b$ or $|w|_a=|w|_b\}$. Currently I have an automaton which recognises that language if $|w_a|=|w|_b$ xor $|w_a|=|w|_c$. ...
271 views

### I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free

How would you go about proving that this Language is Context free. I'm having issues with drawing the PDA for this. I need to prove Prove that the language L = {w | number of 11s in w is more than ...
643 views

### Decidability of Context free languages

Is is decidable whether 2 given PDAs accept the same language? Also, is it decidable whether the language accepted by a given grammar is context free (the given grammar could be unrestricted but ...
111 views

### Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
147 views

### Push-down Automata problem

I understand that a PDA is an automata with a stack (LIFO) but I still can't understand how to answer a very simple question like this one. I've read so many pages on it, searched all over Google, ...
359 views

### Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?

I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a ...
2k views

### Constructing a PDA for the language $\{ 0^n 1^m | n ≠ m \}$

Could anybody help me design a PDA for the language $\{ 0^n 1^m | n ≠ m \}$? Here is what I currently have:
329 views

### Does a PDA follow a transition if the top stack symbol doesn't match?

Does a PDA only move states when both the input symbol matches and the symbol on the top of the stack matches? In other words, is it possible to have two different transitions that both take the same ...
223 views

### How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
217 views

### When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

Options given were: (a) 2 (b) 3 (c) 4 (d) 5 This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but ...
203 views

### CFG for a rather complex language

I'm trying to construct a context free grammar for the language $\{a^ib^j:2i\neq3j+1\}$. I found that when $j$ is even, there are no problems. When $j$ is odd, there are some constraints on $i$. Now ...