Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
539
questions
1
vote
0
answers
117
views
Why do PDAs always halt?
Can’t a PDA get stuck in a cycle of blank transitions?
Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases.
Does the ...
- 191
1
vote
1
answer
1k
views
NPDA which accepts all the strings of a's and b's that have equal number of a's and b's, but do not end up with an a
I have to design an NPDA(Non-Deterministic Push Down Automata) for all the strings over
$\{a, b \}^*$, which have equal numbers of $a$'s and $b$'s but do not end up with an $a$.
I know how we should ...
1
vote
1
answer
244
views
Determine the language of the NPDA
I have to write the language of the below $NPDA$(Non-Deterministic Push Down Automata).
I think that from $q_0$ to $q_1$ and then $q_2$, we are actually building the below all the strings of $0$'s ...
1
vote
1
answer
161
views
Why DFA's configuration space is finite and PDA configuration space is infinite?
I read from this post the term configuration space. I don't know the meaning of configuration space.
What is the exactly meaning of configuration space?
And why DFA's configuration space is finite ...
- 346
2
votes
0
answers
25
views
Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate]
The question is from my homework: Is the language $\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$ a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ...
0
votes
1
answer
191
views
Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n
It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
- 1
1
vote
1
answer
294
views
Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language
I was solving some exercises about CFL from past years' homework and faced this question.
Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
- 453
0
votes
0
answers
133
views
Constructing a PDA for the language of words $uv$ such that $2|u| = 3|v|$
Consider the language $\{ w=uv : 2|u|=3|v|, u,v \in \{a,b\}^+ \}$.
How to compare the lengths of the words? How to know where is the end of $u$ and the beginning of $v$?
What algorithm is used for ...
- 1
-4
votes
1
answer
179
views
Creating a PDA that accepts the following language
Using automata-lib 5.0.0 (Python library), I need help creating a Python program that simulates a PDA that only accepts the following language:
L = {a^m b^n | 0 ≤ m != n}
If you could provide any ...
- 1
2
votes
1
answer
1k
views
Useless states in a PDA
I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads:
4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
- 123
0
votes
1
answer
45
views
Why do non Context Free languages need more stacks?
In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.”
We haven’t delved into CS and reclusively enumerable languages much ...
- 225
1
vote
1
answer
322
views
Why is $a^mb^nc^pd^q$ with $m+p=n+q$ context-free?
$L = \{$$a^mb^nc^pd^q \mid m+p = n+q,$$\text{ where } m, n, p, q \geqslant0\}$
If, for instance, we try to construct a PDA for a similar language
$L2 = \{$$a^mb^nc^pd^q \mid m=p $ $\text{and}$ $ n=q,$$...
- 133
1
vote
1
answer
318
views
If the Pushdown-Automaton for a language is deterministic, is the language non-ambiguous?
For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the ...
- 29
1
vote
1
answer
125
views
Proof no DPDA can accept Palindrome (need explanation for the attached proof)
The given proof for proving that no DPDA can be constructed to accept palindromes is unclear. There exists another similar question but it only explains the proof partially.
I understood how it aims ...
- 11
0
votes
1
answer
730
views
Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free
Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free.
Hi I'...
1
vote
2
answers
205
views
Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
2
votes
1
answer
912
views
PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$
I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$
I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character ...
- 135
0
votes
1
answer
326
views
DPDA by empty stack
Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just ...
- 3
0
votes
1
answer
148
views
How to design PDA for this language?
I'm having a hard time trying to build the PDA for this language:
$$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$
I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
user145974
0
votes
1
answer
125
views
Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$
Construct a PDA, which recognizes the following language $L$: $L = \{w\;|\; |w|_a > 2|w|_b\}$, so it is the language that consists of words which have more than twice as many $a$'s as $b$'s.
I ...
- 131
0
votes
1
answer
50
views
What kind of words does this PDA accepts
I have a PDA A = ({q0, q1}, Σ = {a, b}, Γ = {a}, δ,
F = {q1}), with these transition functions δ:
((q0,a,ε),(q0,a));
((q0,b,ε),(q0,a));
((q0,a,ε),(q1,ε));
((q1,a,a),(q1,ε));
((q1,b,a),(q1,ε)).
The ...
- 3
1
vote
2
answers
83
views
PDA with multiple element access - $i$ - access PDA
We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$.
Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
- 15
1
vote
1
answer
339
views
How can I combine 2 PDA's into 1 PDA deterministically?
I have two PDAs one with $\{a^i b^j \mid i > j\}$ and the other $\{a^i b^j \mid i < j\}$.
I know how to combine these two PDAs non-deterministically. My question is how do I combine these two ...
- 11
0
votes
1
answer
88
views
Difference between Counter-machine and stack machine
I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).
My question is counter machine means counter coexist ...
- 346
0
votes
1
answer
210
views
Why finiteness problem of CFL is decidable?
We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
- 346
1
vote
1
answer
261
views
Why equality is decidable for regular language but not for $CFL?$
There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$
But also there are infinitely many different $DFA$ exists for same regular language. ...
- 346
2
votes
1
answer
336
views
How does Sipser's 0n1n PDA reject 0101?
In Sipser's Theory of Comp in 2.2 the following PDA is provided for ${\{0^n1^n|n\ge0}\}$.
I follow how to process "", ...
- 162
2
votes
2
answers
275
views
Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $
I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
- 346
0
votes
1
answer
157
views
The same transition twice in Pushdown automata (PDA)
If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example.
We start push each letter we ...
-1
votes
1
answer
53
views
I can't get the commands? each of which includes $~\$~$ instead of $~\epsilon~$ of the pushdown automaton
The pushdown automaton is given as the below diagram.
What I know are as below.
$$ 1,0 ~\texttt{->}~ \epsilon_{} ~~ \leftarrow~~ \text{As 1 is inputted then 0 will be popped from the stack} $$
$...
0
votes
1
answer
122
views
Convert a PDA with transition for a state to itself to another PDA
Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this?
EDIT (My thoughts):
I guess we can ...
0
votes
1
answer
140
views
Poping a symbol on a PDA when Input and Stack are Irrelevant
Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
1
vote
2
answers
79
views
Deterministic Pushdown Automata that accepts #a = #b
I am trying to create a DPDA that accepts words from the following Language:
$$
L = \{wx \; | \;w \in \{a,b\}^*, \#a = \#b \}
$$
My intuition was to initially put an $x$ on the stack and then write an ...
- 13
0
votes
1
answer
105
views
Prove that grammar accepting arithmetic expressions is not regular
I created a grammar which accepts all arithmetic expressions consisting of $+,-,*,/, (, )$.
I created the following grammar:
$S \rightarrow M+-M$
$+-M \rightarrow +M+-M$
$+-M \rightarrow -M+-M$
$+-M \...
- 3
0
votes
0
answers
40
views
pushdown automata question
We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
0
votes
1
answer
325
views
How to show that pda accepts empty language?
I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski ...
- 21
0
votes
1
answer
110
views
Pushdown automaton with binary stack
I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language ...
- 1
1
vote
0
answers
44
views
Unambiguous formal grammars for a specific class of languages
Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$.
Now suppose that $q \in \mathbb{Q}$ is a positive ...
- 131
1
vote
1
answer
58
views
PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$
On my compilation theory exam we had the following problem:
Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
- 71
0
votes
1
answer
67
views
PDA accepting of a specific symmetric language
Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$.
if we have $a$ This side of the string, on the other side of the string we have $aa$.
and if we have $b$ This side of the ...
- 75
0
votes
1
answer
202
views
Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$
How can I construct a PDA which accepts the language $\{a^i b^j c^k \mid k\geq \min(i,j)\}$
I think about different solutions such as building a stack with two-state. one state is for $i < j$ and ...
- 75
0
votes
0
answers
805
views
Is this PDA correct for L = {0^m1^n | n ≤ m ≤ 2n}?
I have drawn this transition diagram for the given language. Is this correct?
- 115
0
votes
1
answer
108
views
PushDown Automata
Let Sigma = {a,b,c} and let L be the language of all words in which all the a’s come
before the b’s and there are the same number of a’s as b’s and arbitrarily many c’s that
can be in front, behind, ...
- 3
2
votes
1
answer
173
views
Proof that class of languages accepted by DPDA by empty stack is not closed under union
My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):
$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
- 125
0
votes
1
answer
711
views
CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s
I'm trying to find the CFG and PDA for the above language. I have so far come up with this
$S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$
However, I realized that this is just a subset of the ...
- 7
0
votes
0
answers
127
views
Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$
I'm trying to find the PDA of the above language. I understand that this is the complement of the language
$L_1=\{w : w=a^nb^n : n\geq0\}$
However, I can't understand the idea behind constructing the ...
- 7
-1
votes
1
answer
404
views
PDA for $\{a^ib^jc^k \mid (i+j) \bmod 3 = 0, k = i + j\}$
Construct a pushdown automaton that accepts
$$\{a^ib^jc^k \mid (i+j)\bmod 3 = 0, k = i + j\}$$
-1
votes
1
answer
186
views
PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }
I have seen this similar question
but I can't seem to apply the same technique for the equation $7j = 5i + 6k$
1
vote
1
answer
70
views
Extended NPDA implementation
In Formal Grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several ...
- 11
2
votes
1
answer
119
views
Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$
I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try:
I know that context-free languages are closed under union operation. Also I know how to make a PDA for ...
- 67