Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
90
questions
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
5
votes
2
answers
47k
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 $...
- 449
51
votes
2
answers
46k
views
Is a push-down automaton with two stacks equivalent to a turing machine?
In this answer it is mentioned
A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
- 1,077
8
votes
1
answer
4k
views
prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?
Is ...
- 991
17
votes
1
answer
11k
views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
- 305
4
votes
3
answers
9k
views
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$
My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
- 51
40
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.8k
12
votes
5
answers
2k
views
is it possible to minimize pushdown automata?
is it possible to minimize pushdown automata?
If no, why?
Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
- 121
11
votes
1
answer
947
views
How to prove that ε-loops are not necessary in PDAs?
In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
- 72k
7
votes
1
answer
2k
views
Removing $\epsilon$ transitions in a NPDA
NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.
However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
- 93
3
votes
3
answers
3k
views
Why DCFL is not closed under kleene star?
I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
user52152
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
1
vote
2
answers
3k
views
When generating a PDA from a CFG do I have a receiving state?
Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
user10392
0
votes
2
answers
863
views
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
We know that $L
= \{ xy | x, y \in (0 + 1)^*, |x| = |y|,
x≠y\}$
is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
- 346
9
votes
2
answers
3k
views
Decidability of halting problem for DPDAs with $\epsilon$-transitions?
For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.
But what about PDAs with $\...
- 743
8
votes
1
answer
5k
views
Are DCFLs closed under reversal?
According to this chart, DCFLs are closed under reversal.
However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
- 259
7
votes
2
answers
1k
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 ...
- 431
6
votes
2
answers
3k
views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
- 163
4
votes
1
answer
471
views
Proof that PDA's with different definitions have same expressive power
Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$,
where
$Q$ is the set of states,
$\Sigma$ is the input alphabet
$\Gamma$ is the stack alphabet
$\delta$ is the transition function ...
- 43
3
votes
1
answer
674
views
How to prove that a bounded pushdown automaton is regular?
I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain ...
- 33
3
votes
1
answer
3k
views
How can one simulate a PDA with a FIFO queue PDA?
I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
- 83
3
votes
1
answer
8k
views
Pushdown automaton for complement of { ww | ... }
I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).
So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not ...
26
votes
3
answers
2k
views
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$
As pointed out by sdcvvc, a word in this language can also be ...
- 747
24
votes
1
answer
4k
views
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)
There may also exist a Deterministic Pushdown ...
- 709
9
votes
1
answer
3k
views
Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
- 2,932
9
votes
1
answer
27k
views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
- 227
8
votes
2
answers
4k
views
How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
I have tried to reduce this problem to another undecidable ...
- 1,587
6
votes
1
answer
2k
views
pda: transformation between acceptance by empty stack and final states
I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
- 63
6
votes
2
answers
1k
views
Intersection of two NPDAs
Is there a way to take the interection of two NPDAs?
I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
- 1,133
5
votes
1
answer
5k
views
Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
- 349
5
votes
2
answers
17k
views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
- 4,259
5
votes
2
answers
5k
views
why are deterministic PDAs not closed under concatenation?
I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this ...
- 1,269
4
votes
1
answer
1k
views
Pushdown automation where number of letter `a` is at least as twice as letter `b` in the word
I have talked to my friend and he said this is the only place somebody could know how to solve it. It is the only exercise(from around 80) from exam revise I just do not know how to do at all.
Create ...
- 41
3
votes
1
answer
3k
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 ...
3
votes
1
answer
105
views
Is "duplicate" in RPN enough for replacing variable binding in term expressions?
I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{...
- 5,382
2
votes
1
answer
337
views
PDA for the language of strings containing the same number of a and b
Need idea for solving the following pushdown automata:
$\mathcal{L}=\{w\in\sum ^* | \#a(w)=\#b(w),|w|\geqslant 0\} \,\,\,\, \sum=\{a,b\}$
In the beginning I thought to PUSH A for input a, and then ...
- 123
2
votes
1
answer
3k
views
Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?
$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $
Is this language a context free language?
If yes give a PDA. If no, give a proof.
The pumping lemma for context free languages doesn't seem to work ...
- 1,269
2
votes
2
answers
940
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 ...
- 1,637
2
votes
1
answer
780
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 ...
- 123
1
vote
2
answers
372
views
Why are pushdown automata countable? [closed]
I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.
The problems in this section are pretty confusing and I honestly don't know how to begin ...
1
vote
1
answer
1k
views
Context Free Grammer and PDA (Palindrome but without characters repeating in a row)
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says
"L contains palindromes that don’t ever have the same character occur twice ...
- 11
0
votes
3
answers
2k
views
Push-down automaton for a language with number of 1s double than 0s [duplicate]
This questions is taken from a complexity theory course.
Design a push-down automaton that recognize $L = x \in \{0,1\}^* $
such that $x$ contains a number of ones double than a number of zeros.
...
- 175
13
votes
1
answer
394
views
Computing the intersection of two NPDA where it is possible
Apropois to Raphael's suggestion on Intersection of two NPDAs:
Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
- 1,133
9
votes
2
answers
906
views
Myhill-Nerode style characterization of CFL?
Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$.
The Nerode equivalence ${\sim}_L$ has ...
- 3,452
8
votes
3
answers
6k
views
Why do pushdown automata use a stack?
I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
- 199
7
votes
1
answer
1k
views
Who first introduced the pushdown automaton?
I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
- 9,037
7
votes
3
answers
13k
views
Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$
I'm having a lot of trouble constructing a PDA for the language: \begin{equation*}
\{a^m b^n : m < 2n < 3m \}
\end{equation*}
I know if I push a symbol for each $a$ I see, then pop 2 symbols ...
- 232
6
votes
1
answer
855
views
Undecidable problem intersection of two DCFL languages is DCFL?
We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
- 201
6
votes
1
answer
6k
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 ...
- 431
5
votes
1
answer
375
views
Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$
So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ ...
- 29.6k