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
129
views
Question about proof of Lemma 2.41 - Sipser book
Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ...
- 111
0
votes
1
answer
121
views
Formal definition of a language accepted by PDA
I am a bit confused on how to give a formal definition of the language accepted by A?
I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" ...
- 1
-3
votes
1
answer
349
views
PDA for parentheses language
Construct a PDA for the language described by the following CFG:
$$ S \to [S] \mid \{S\} \mid \Lambda $$
How can I develop a pushdown automaton for this language?
0
votes
1
answer
138
views
PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$
I'm pretty new to the PDA topic.
How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$
I've tried all the possibilities, but I still somehow end up accepting all words.
- 9
-1
votes
1
answer
843
views
How to convert NPDA to PDA?
I have been given this Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be ...
-1
votes
1
answer
2k
views
How do I convert this PDA to CFG?
How do I convert this PDA to CFG?
I am currently stuck with this, any help would be appreciated, thank you in advance!
0
votes
1
answer
260
views
The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
- 1,112
2
votes
1
answer
225
views
Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?
I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
- 163
1
vote
2
answers
282
views
Is it decidable for a NPDA to halt?
I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string.
But are there ...
- 461
1
vote
0
answers
190
views
A pda that accepts all strings over an alphabet
If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is
L={w | w belongs to (a,b,c,d)*}
How would that be constructed? My idea is to have one state as ...
- 11
1
vote
0
answers
147
views
How does a PDA compare two configurations of accepting histories?
In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...
2
votes
1
answer
473
views
How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?
After defining pushdown automaton in Sipser's book at p. 113:
at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:
My question is about the part "...
- 43
0
votes
2
answers
971
views
In a NPDA if the stack is empty, where the start/end state are the same can you go again
Thoughts
I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ...
- 11
-1
votes
1
answer
31
views
Find CFG for the following language
I need to show that the following language is context free:
$$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}$$
- 7
1
vote
0
answers
427
views
Determine the language of the given NPDA
Thoughts
I am wondering is the language $ab^*$, since $a$ pushes $X$ to the stack and $b$ pops, and if there is an $a$ there has to be a $b$ to get back to the final state?
Also, is it right to say $...
- 11
0
votes
2
answers
75
views
For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)
Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0}
I’m trying to design a PDA. My aproach is:
-for every 2 ‘a’ push an ‘a’
-for every 4 ‘c’ push a ‘c’
-then pop them ...
- 7
4
votes
1
answer
1k
views
Prove or disprove {wtw^R | |w| = |t|} is context free
The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$
It looks like the language can be "pumped" by context free pumping lemma, ...
- 361
1
vote
2
answers
121
views
Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?
My assignment asks
Let $S =
\{
w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star
; (∃i < k) w_i\neq w_{i + 1}^r$
, i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
- 21
0
votes
1
answer
182
views
Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?
I recently found a question asking whether the language given below is context-free or not:
$L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$
My intuition is that I can design a non-deterministic push-down ...
1
vote
1
answer
39
views
Developing a Context Free Grammar whilst knowing the number of terminals
I am trying to develop a CFG for the language $L$ defined by:
$L = \{a^{n+2}bba^{n-2} | n > 1\}$
The problem I am having is that I cannot develop the CFG for this language no matter what I try. ...
- 113
0
votes
1
answer
407
views
Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}
I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option.
NPDA are not very intuitive to me. The only solution I found online is:
I don‘t ...
- 7
0
votes
1
answer
250
views
Pushdown automaton from given code for parsing a while statement
I was preparing for my exam and have some questions that can possibly come on the test.
There is a task to make pushdown automata from a given code:
...
user115005
1
vote
1
answer
285
views
Can there be a language not Context free but still PDA acceptable?
Let the input alphabet be $Σ = \{1,x,=\}$
Let the stack alphabet be $\tau = \{1,\$\}$ where $\$$ is the initial stack symbol.
Let,$q_0$ be the initial state of the PDA,$q_f$ be the final state of PDA,...
- 281
1
vote
2
answers
2k
views
How Intersection of Regular Language and a CFL is a CFL?
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then
L1 intersection L2 is not a CFL
And we know, all Regular languages are CFL. Then ...
0
votes
0
answers
106
views
What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?
It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
- 123
0
votes
1
answer
100
views
Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:
$\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $
...
2
votes
1
answer
1k
views
Why no DPDA can accept Palindrome? (according to this proof)
This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin.
My question is from the pink part at the second page:
It follows in particular that no ...
3
votes
2
answers
235
views
Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?
$ \# a^nb^{2^n} \# $
such that
• The alphabet of the machine is {, a, b, x}.
• The symbol x will never appear on the input a.
• The contents of the tape at completion may be anything.
• The head ...
- 31
1
vote
1
answer
1k
views
Creating a Deterministic Push-Down Automaton for the Union of two languages
Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
- 156
0
votes
0
answers
89
views
Prove that any PDA/CF language with 1 character is regular [duplicate]
I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
- 85
2
votes
1
answer
303
views
Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?
I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
- 147
3
votes
1
answer
402
views
Does this argument prove CFLs are not closed under union?
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
If CFLs were closed under complementation, then they must have also ...
- 33
2
votes
0
answers
224
views
Is the following PDA a DPDA or NPDA?
Let the language be : $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}. $$
Now the PDA that I've designed for this language and seen at many other places is :
...
- 93
0
votes
0
answers
245
views
Pushdown Automata for number of a less than 2 times number of b
Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works?
we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
- 231
1
vote
1
answer
334
views
Is Half - Palindrome subset of a context-free language context-free?
Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
- 231
3
votes
2
answers
3k
views
Proving the decidability of whether a CFG generates a particular string or not
Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.
Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
- 111
1
vote
1
answer
863
views
Can you create a deterministic PDA for non-palindomes?
Using non-determinism to create a PDA to recognize non-palindromes is easy.
My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.
- 21
0
votes
0
answers
505
views
Constructing a PDA to accept the language {a^i b^j c^k where i,j,k>0 and i<=j<=2k}
Can anybody help me out with this? If I try to compare $a$'s with $b$'s to check if $j\ge i$ then I won't be able to compare the same number of $b$'s with the number of $c$'s that is to check if $j\le ...
- 1
1
vote
0
answers
184
views
Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs
I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)
...
0
votes
1
answer
1k
views
Pushdown Automata - can you have multiple transition functions options between 2 states?
I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?
For example,
...
2
votes
2
answers
58
views
DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$
I need some help with the following task:
I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$.
How can I recognize that the new ...
0
votes
1
answer
2k
views
Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s
Design a Pushdown Automata, accepting either by final state or by
empty stack to accept the set of all strings of 0’s and 1’s such that
no prefix has more 1’s than 0’s
This is a homework question,...
- 103
1
vote
0
answers
78
views
What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?
Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code.
...
- 111
5
votes
3
answers
3k
views
Context-free grammar of the concatenation of a string S and subsequence of reversed S
I have to find a Context-Free grammar that generates the language:
$L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$
The concatenation of two mutually ...
- 137
6
votes
1
answer
1k
views
A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
It is known that a PDA with two stacks is equivalent to a TM.
On the other hand a PDA with one stack is capable to recognise only context-free languages.
Hence there is a kind of a gap between the ...
- 345
1
vote
1
answer
395
views
It is decidable whether a pushdown automaton will accept a word? [duplicate]
I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.
I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
- 113
1
vote
2
answers
2k
views
L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.
I need to Show that L is decidable.
I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
- 13
4
votes
1
answer
212
views
Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?
In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1]
In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
- 205
1
vote
0
answers
101
views
How to visualize non-deterministic pushdown automata?
My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
3
votes
1
answer
329
views
Is the halting problem solvable for NPDAs?
After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
- 1,682