Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
537
questions
4
votes
3
answers
1k
views
Are 2 independent PDAs equivalent to a turing machine?
I was thinking about the language a^nb^nc^n, which is obviously not context free, but if we run it through 2 automata at the same time (the first for ...
- 51
-3
votes
1
answer
93
views
DPDA for language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$
How to construct DPDA for the following language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n $
$L_1 = \{a,b\}^* \setminus a^nb^n =\{a^i b^j \, | \, i>j\}\,\cup\,\{a^i b^j\ \ | \ i<j\}\,\cup\...
- 25
-1
votes
1
answer
71
views
Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.
For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
- 3
0
votes
0
answers
49
views
Constructing an equivalent Pushdown Automaton
I'm working on an exercise (not relevant for evaluation) that involves constructing an equivalent nondeterministic stack machine from a given machine with epsilon-transitions. However, I'm having ...
- 125
0
votes
0
answers
32
views
can a DPDA have two transition to different states when you pop a different symbol?
I have a question about the DPDA. Is it possibly to have two transitions that read the same input but do different in the stack?
An example would be A transition from q1 to q2 where I read input ( pop ...
- 3
0
votes
1
answer
39
views
can you read and push different symbols in a DPDA?
I have an easy question about the DPDA. Could you read an input and push a different symbol to the stack.
An example would be A transition from q1 to q2 where read input is v pop is epsilon(empty ...
- 3
0
votes
0
answers
11
views
Deterministic pushdown automata that checks for a specific variable in nesting levels
I want to define a DPDA based on a set of rules:
one or more uppercase letters ('A'-'Z') is a formula.
one or more lowercase letters ('a'-'z') is a formula.
if X and Y are formulas, then this is a ...
- 1
1
vote
1
answer
75
views
Can a pushdown automaton write more than one symbols on to stack on one reading from from input tape?
The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: . The transition function however only takes in one symbol from the stack (after ...
- 51
0
votes
0
answers
42
views
Equivalent context free grammar for every pushdown automaton?
Equivalent context free grammar for pushdown automata
[edit] This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note ...
1
vote
1
answer
39
views
Simple pushdown automata question
I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not ...
- 67
0
votes
0
answers
56
views
Constructing a PDA for $L=${$\exists i,k\in \mathbb{N} : |w|=2k, w_i \neq w_{k+i}$}
I have the main idea, yet I'm uncertain on how to construct this PDA (in terms of states, transitions)
We can assume the alphabet $\Sigma$ is {$0,1$}, proving for $\Sigma=${$0,1$} is a sufficient ...
- 315
0
votes
1
answer
49
views
How PDA decide when and which state to transform to?
[1] gives an example for PDA which contains rules of:
(p,e,Z,q,Z)
(p,e,A,q,A)
and says,
The third and fourth instructions say that, at any moment the automaton ...
- 103
3
votes
2
answers
2k
views
Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form
Here's what Wiki says:
And here's what Mike Sipser says in his Introduction to Theory of Computation:
The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
- 51
-1
votes
1
answer
49
views
The book says 27 terminals but I only see 10. Where are they?
On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
- 51
1
vote
2
answers
77
views
Need to create CFG that requires sum of other letters
I have a homework assignment that requires me to create CFG $G$ for
$$L = \{a^i b^{i+j+k} c^j d^k\}$$
so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
- 11
0
votes
1
answer
43
views
Pushdown Automata Construction
I had an assignment in which I had to design a pushdown automata that recognizes the language ${w \in [a,b,c]^*|w }$ have the same number of "ab" and "ba".
Tried to make a pushdown ...
4
votes
0
answers
60
views
Is the following language recognizable by a visibly pushdown automaton?
Consider the alphabet $\Sigma = \Sigma_c \cup \Sigma_i \cup \Sigma_r$ separated into call, internal, and return letters. Assume that $c \in \Sigma_c, r \in \Sigma_c$, and $a \in \Sigma_i$.
I have a ...
0
votes
0
answers
55
views
prove that Every DPDA has an equivalent DPDA that always reads the entire input string
I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
- 1
0
votes
1
answer
92
views
PDA for equal number of as and b's where n>=1
How to design Push Down Automata for a language that has equal number of a's and b's where $n \ge 1$?
I got how to do it for $n \ge 0$, not able to get it for $n \ge 1$.
Swathi A
3
votes
2
answers
73
views
Implementation details of "transitions" of Non-deterministic push-down automata
I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata"
He states that the ...
- 305
0
votes
1
answer
66
views
PushDown automata for a^(n) b^(2n) c^(2n) d^(n)
i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)"
i am arguing that there is no pda for that question but our ta says that we can push 5x to the ...
0
votes
1
answer
47
views
What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?
I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
- 21
0
votes
1
answer
47
views
Intersection of CFL and DCFL
Is CFL $\cap$ DCFL = CFL, always true?
CFL - Any Context Free Language
DCFL - Any Deterministic Context Free Language
0
votes
0
answers
34
views
Find a PDA for $\{a^*b^*c^*\}\setminus \{a^nb^nc^n\mid n\geq 0\}$
Basically the set $$\{a^*b^*c^*\}\setminus \{ a^nb^nc^n\mid
n\geq 0\}=\{a^nb^mc^k\mid n\neq m\}\cup \{a^nb^mc^k\mid m\neq k\}$$Now for $$\{a^nb^mc^k\mid n\neq m\}=\{a^nb^mc^k\mid n>m\}\cup\{a^nb^...
- 133
1
vote
1
answer
82
views
Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".
The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
- 13
0
votes
0
answers
29
views
PDA to CFG: when to know if its a useless rule
If we are given a PDA and told to convert to a CFG, I am confused just in general how to determine how we figure out if a rule is a useless rule. I know you for this rule that its useless: if we have ...
- 1
0
votes
1
answer
45
views
Push Down Automata
I am learning about context free languages.
I understand how $\{a^nb^nc^n|n>0\}$ can be shown to be not context free using the pumping lemma for CFL's.
Intuitively however it seems that a pushdown ...
- 1
1
vote
1
answer
485
views
Understanding this PDA for non-palindromes over {0,1}
I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
- 11
0
votes
1
answer
35
views
Context Free Language Twist [duplicate]
I am trying to recognize a particular language,
L= {a^n b^k | n<=k<=2n}
and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count ...
2
votes
0
answers
82
views
Minimizing DPDA
Is there an efficient algorithm for minimizing a deterministic PDA in terms of states? Is it even computable?
I know that it is not possible to minimize a PDA in general, but my question is about ...
- 208
2
votes
2
answers
195
views
Intuition for Sipser's proof of PDA to CFG
I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two.
He splits the proof (...
- 33
0
votes
0
answers
280
views
Non-deterministic Pushdown Automaton to Context-Free Grammar
While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question:
Find a CFG for the following NPDA $M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
- 101
1
vote
1
answer
63
views
Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous
Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous.
The CFG is as follows. $G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$
where $R$ consists of 6 rules:
$E\...
0
votes
3
answers
133
views
Is Turing completeness necessary?
Most programming languages are Turing complete (finite memory blah blah blah), and when we design languages this is a goal.
But is it really necessary? What algorithms do we typically use that require ...
- 91
-1
votes
2
answers
71
views
Is this a context free language? I need to make PDA but I don't think it is doable
I got a question:
Design a pushdown automata that can recognize strings in L= {$ a^n b^{2n} c^{3n} | n ≥ 0 $} .
I tried to think and design it, but I couldn't find it. The best that I can think of is ...
- 1
1
vote
3
answers
370
views
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL.
Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$.
When I separate to cases, ...
- 239
2
votes
2
answers
138
views
in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?
I'm struggling with the definitions of the push-down automata. In 2-DPDA and 3-DPDA, what do the numbers 2 and 3 stand for: for the number of stacks or of read-only tapes (and hence RO heads) ?
...
- 23
-1
votes
1
answer
302
views
Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
To those of you who saw my post from an hour ago - I deleted it because I came up with an idea.
To summarize, I have to design a PDA for this language, without using the usual method of firstly ...
- 155
1
vote
1
answer
216
views
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
$L= \{ a^nb^m | n \le m \le 2n \}$
As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
- 155
0
votes
1
answer
683
views
Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $
$L = \{a^nb^m | n \le m \le 3n \} $
This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each ...
- 155
0
votes
1
answer
80
views
Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$
Could someone please help me check if my automaton is correctly designed?
$$L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$$
This was an exercise from our workbook, but their solution is a ...
- 155
0
votes
1
answer
303
views
Sets of problems in different models of computation and cardinality
In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg
Essentially, Pushdown Automata (PDA) can solve ...
- 19
1
vote
2
answers
170
views
Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?
If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata?
Bonus question: Can ...
- 11
1
vote
2
answers
106
views
Pushdown automaton that accepts $a^{2k} b^{3k}$, without multiple pop
I am trying to create a PDA with at most 7 states that accepts the following language over the alphabet $\Sigma = \{a,b\}$:
$$
\{a^{2k}b^{3k} \mid k \geq 0\}
$$
The tricky part is that multiple push ...
0
votes
2
answers
684
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
0
votes
1
answer
596
views
How to prove ww^r is context free using pumping lemma for context free languages
I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
- 305
1
vote
1
answer
222
views
An exercise that asks for informal description of the language accepted by a specific PDA
This is a problem that I have found from Introduction to automata theory, languages and computation by John Hopcroft and Jeffrey Ullman.
PDA P=({q0, q1, q2, q3, f)}, {a, b}, {Z0, A, B}, δ, q0, Z, {f}) ...
- 13
0
votes
1
answer
242
views
Build a 2-PDA for language accepted by Turing Machine
I saw this question on the internet and found many solutions actually but none of them really persuade me that much.
Question: Given language $L$ which is accepted by a Turing machine $M$, provide a 2-...
- 453
1
vote
0
answers
105
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 ...
