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
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
2
votes
2answers
21k 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 $...
0
votes
1answer
155 views

Pumping lemma to show a language is not context free [duplicate]

I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start ...
1
vote
0answers
350 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
2
votes
1answer
2k views

Confusion about Definition of DPDA and $\epsilon$-move

The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA. I tried it, then I confused the definition! By definition, I could construct these $\delta(q_1,...
0
votes
1answer
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 ...
2
votes
1answer
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. ...
1
vote
1answer
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 ...
-2
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
3answers
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
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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?
0
votes
3answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
5
votes
3answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
777 views

Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
5
votes
2answers
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 ...
0
votes
1answer
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. ...
0
votes
1answer
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\}$
3
votes
1answer
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 ?
1
vote
0answers
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$ : ( ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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$. ...
1
vote
1answer
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 ...
-2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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, ...
3
votes
1answer
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 ...
-1
votes
2answers
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:
3
votes
2answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
6
votes
0answers
201 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 ...
2
votes
1answer
845 views

CFL and inverse homomorphism

I found a proof that shows CFL is closed under inverse homomorphism. First of all the Definition of an homomorphism and its inverse: $h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in ...

1 2 3 4 5 8