Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [pushdown-automata]

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

360 questions
Filter by
Sorted by
Tagged with
957 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 ...
2k 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 ...
664 views

Conversion from nondeterministic PDA to deterministic PDA

Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
684 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 ...
137 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 ?
318 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$ : ( ...
226 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 ...
51 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 ...
490 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 ...
814 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 ...
239 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 ...
613 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 ...
641 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 ...
405 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$. ...
239 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 ...
565 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 ...
100 views

Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata  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 ...
118 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, ...
352 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:
275 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 ...
165 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 ...
185 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 ...
164 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 ...
163 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 ...
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 ... 1answer 328 views How do I normalize a push down automaton? Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from$q_1$to$q_1$, because I know a transition must either push OR pop from the stack. Does ... 1answer 475 views A PDA to recognize the Intersection of two regular languages? I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages: Intersection of L1 and L2 L1 = L (aaa* bab) L2 = L (aab* aba)... 2answers 189 views Upper bound for the union of$n$DFAs of size at most$m$? Let$\Sigma$be an alphabet of size$2$, and let's consider$n$regular languages$L_i \subseteq \Sigma^*$respectively recognized by$n$minimal DFAs$D_i$whose size are bounded by$m$. As the ... 1answer 186 views Push-down Automata Construction Construct a push-down automata to recognize the language$ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here,$v^{\complement}$is the bit-complement of v. I don't see how to perform ... 1answer 286 views Determining whether$ L = \{ 0^n1^{n^2} | n \ge 0 \} $is a CFL Assuming$L$is defined as follows: $$L = \{ 0^n1^{n^2} | n \ge 0 \}$$ I'm trying to either prove/disprove whether$L$is CFL or not. My intuition tells me its not CFL since I cannot express the ... 0answers 295 views Constructing a minimal pushdown automaton for counting characters in substrings I have to construct a pushdown automaton for the following language over alphabet {a,b,c}: L={ ucv | |u|!=|v|; u,v={a,b}* } (note: u,v are substrings over alphabet {a,b}, |u| is length of substring ... 1answer 43 views Is a String with no parantheses considered having balanced parantheses? Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses. Clearly x(), (xy) , ()()xxx, ((xx)) are accepted. BUT My ... 2answers 378 views Push down automaton for Language of same number of as and bs The task Find a pushdown automaton$M$, so that$L(M)=\{w \in \{a,b\}^*\ |\ |w|_a=|w|_b\}$, where$|w|_a$denotes the number of$a$s in a word$w. My solution I'm using the Wikipedia notation. $$... 1answer 257 views Simulate NPDAs with DTMs using only polynomial overhead We know by polynomial-time parsing algorithms like the classical CYK algorithm that \mathrm{CFL} \subseteq \mathrm{P}. Furthermore, it is easy to show by direct simulation that \mathrm{DCFL} \... 0answers 101 views Why is DCFL not closed under kleene star? [duplicate] I honestly haven't an idea how to proof that eventhough I can understand the background, could someone help me? 0answers 275 views Create PDA for the alphabet {a,b} starting and ending with the same symbol [duplicate] I have to design PDA accepting language: set of strings over ∑ {a, b} starting and ending with the same symbol. From that moment i think good way is to remember only first element because the last one ... 1answer 307 views Equivalent DPDA that always halts for every DPDA with empty stack language I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts. my transition function of P is \... 1answer 47 views What can be said about the given language? L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup \left \{ aab^ka^{2k} | k>0 \right \} What can be said about the given language L ? According to me, I think it is CFL and not DCFL as I tried ... 2answers 1k views When does a PDA halt? In DFA/NFA the automaton halts when it finishes reading the string. In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or ... 0answers 68 views How can I build this automaton? The automaton has to recognize the language (a^n)(b^m) so the number of bs is at least the number of as and at most twice that number. The only thing I have achieved is to get an automaton that ... 1answer 447 views Algorithm to detect if word belongs to pushdown automaton I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that. My thought at first would be to go ... 1answer 234 views How to represent a double push or double pop operation in push down automata I want to know the theoretical representation of a double push or a double pop in pda 1answer 2k views Push down automata acceptance by Empty stack and final state I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states ... 1answer 1k views PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it I know the grammar for the language \{ xy : |x| = |y|, x ≠ y \} if \Sigma=\{a,b\}:$$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*}$I ... 1answer 83 views How do you read this context-free language? say you want to make a Pushdown Automaton to recognize this language. What exactly does the +1 mean? I see in the example it just pushes an a to the stack before arriving at an acceptance state but I ... 2answers 78 views Context free grammar issue at pda I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata. The automaton accepts all strings over alphabet$\{e,k,q,y\}$of the form$w\...
I am stuck on a problem involving PDA's and CFG's. The problem is as stated: Give a CFG and a PDA for the language of regular expressions over the alphabet $\{a, b, c\}$. Give the formal tuple ...