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.

Filter by
Sorted by
Tagged with
5
votes
3answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
664 views

Conversion from nondeterministic PDA to deterministic PDA

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

How can I build this automaton?

The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number. The only thing I have achieved is to get an automaton that ...
2
votes
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 ...
1
vote
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
0
votes
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 ...
3
votes
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 ...
1
vote
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 ...
0
votes
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\...
2
votes
1answer
665 views

PDA and CFG of language of regular expressions

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 ...