Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
539
questions
3
votes
1
answer
263
views
Proof emptiness for PDA is $\mathcal{O}(n^3)$
It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is ...
- 385
0
votes
0
answers
91
views
Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]
I am studying push down automata.
When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
4
votes
0
answers
336
views
Detecting loops in NPDAs
I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
- 1,682
-1
votes
1
answer
937
views
Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }
$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$
I have trouble about this PDA. Anybody can help me about draw this PDA?
0
votes
2
answers
4k
views
aⁿbⁿcⁿdⁿ using 2-stack PDA
I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$.
Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
- 133
1
vote
1
answer
352
views
Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity
I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there ...
- 11
2
votes
0
answers
45
views
kPDA handling multiple epsilon transtions
I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with ...
3
votes
0
answers
33
views
Automaton without stack for visibly pushdown languages
This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...
- 385
0
votes
1
answer
36
views
Behavior of specific PDA for a certain input
Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push ...
- 3
0
votes
0
answers
269
views
How can I find a language from a given PDA
I have the following PDA:
And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
- 47
1
vote
1
answer
227
views
Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]
How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?
I'm sorry I can't give any approach of what ...
- 11
-1
votes
1
answer
85
views
How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$
I don't have any idea. Can someone help me.
- 53
0
votes
1
answer
517
views
Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $
Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-...
- 53
1
vote
1
answer
154
views
NPDA transitions to different states by taking same input and popping same top element of a stack
Suppose i have some NPDA and there is some transition functions defined as:
$\delta(q_{1},a,A) = (q_{2}, A)$
$\delta(q_{1},a,A) = (q_{3}, Z)$
Is it allowed?
I understand, that since the NPDA is ...
- 13
2
votes
0
answers
2k
views
Turing machine VS Push Down Automaton in CFL
I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why?
I know that a pushdown automaton can ...
- 97
1
vote
1
answer
1k
views
Allowing an empty (epsilon) transition in a PDA
I'm trying to allow an empty transition in a PDA for the following language:
Alphabet: $Σ = \{a, b, c\}$
Language: $L = \{ a^ib^j \mid i \neq j \} \cdot \{ c \}^\ast$
Examples of words in $L$:
$\...
- 135
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
1
vote
1
answer
4k
views
Constructing a PDA with an unequal number of a/b
I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf
I found question 3g to construct a pushdown automata for the following:
{$ {a^i b^j}$ | ${i \neq j}$}
...
- 135
1
vote
1
answer
102
views
How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?
I think this could be a good exercise and the conditions are ...
- 527
1
vote
1
answer
56
views
Grammar of words with exactly $k$ prefixes in another grammar
Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that
$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$
where $\text{Pref}(w)$ is the set ...
- 416
0
votes
1
answer
1k
views
Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$
How can I construct a PDA which accepts the language
$\{a^ib^j \mid 0 \leq j \leq 2i\}$?
1
vote
2
answers
982
views
Does left factoring CFG make it unambiguous?
I came across following problem:
If the CFG is left factored then it must be Unambiguous and Not left Recursive.
TRUE/FALSE?
I have many thoughts about this. But I feel they are somewhat ...
- 1,637
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
1
vote
1
answer
86
views
Constructing a pushdown automaton that accepts L*
Would appreciate if you could take a look at what I did and help me finish it.
Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*...
- 23
1
vote
2
answers
428
views
Formal definition of an empty stack accepting PDA
PDA's are usually defined using the 7-tuple convention.
$M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$
F is the set of accepting states.
I want to design a PDA accepting by empty stack, so using ...
- 211
0
votes
1
answer
165
views
Construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$
I have to construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$
So my idea is to (informally) not pushing anything into the stack while having 0s at first, then when automata start accepting 1s it should ...
- 1
0
votes
1
answer
653
views
What is the set of languages accepted by empty stack pda?
I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?
0
votes
1
answer
57
views
Is the language $(a^n)^mb^n$ context free?
$(a^n)^mb^n$ for $m,n\ge 1$
This can be rewritten as $a^{nm}b^n $
i.e. number of $a$'s is a multiple of number of $b$'s, or for every m $a$'s there is one $b$. I thnk this language can be accepted ...
- 117
1
vote
1
answer
355
views
Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?
Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and ...
2
votes
1
answer
594
views
How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount
I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is
$$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
-1
votes
3
answers
7k
views
why can not NPDA is equal to DPDA?
I have recently read that turing machine can be remodeled to perform as PDA now, i have a question that since DTM = NDTM ( non deterministic Turing machine) then every DTM can remodeled to be NDTM ...
- 329
2
votes
1
answer
1k
views
How prefix property of language affects the PDA
I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this ...
- 329
0
votes
1
answer
1k
views
What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
- 175
1
vote
1
answer
201
views
Context Free Grammer and PDA [duplicate]
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
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
1
vote
2
answers
4k
views
Why is this pushdown automaton for some palindromes right?
$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$
Solution:
For example: $111$ should be accepted
steps are
$q_1 \to q_2$ stack: [$\$$]
$q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$...
- 203
1
vote
2
answers
4k
views
PDA of the language where the number of a's are NOT equal to the number of b's
I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1
...
- 17
2
votes
0
answers
282
views
What is the simplest automaton that can compute the sum of two integers of arbitrary length?
It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length?
I ...
- 121
0
votes
2
answers
2k
views
Construct a Deterministic Pushdown Automaton for unequal number of elements
Can anyone help me construct a deterministic PDA for the following language:
$$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$
Or can anyone check if the following solution is correct?
- 11
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
-1
votes
1
answer
342
views
Convert grammar to Greibach form
The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
- 99
2
votes
0
answers
129
views
Which transducer models replacement in regex?
I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order.
For example: ABC => CAB, which, with ...
2
votes
2
answers
2k
views
PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
- 23
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
0
votes
1
answer
224
views
Can PDA model Turing Complete objects if the objects' state are finite?
I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract.
I am trying to understand the proofs of Chapter 6.
...
- 95
1
vote
0
answers
22
views
Is there anything like equivalence classes in PDA (and more expressive ones, perhaps)?
The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases. However, obviously, DFA cannot ...
- 1,378
3
votes
1
answer
124
views
$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?
A related question:
How to prove that a bounded pushdown automaton is regular?
Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^...
- 249
2
votes
3
answers
653
views
Are all finitely recursive context free languages parseable with a regexp?
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
- 283
-1
votes
1
answer
1k
views
How to convert a CFL to a deterministic PDA?
I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA.
I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
0
votes
1
answer
217
views
Does a pushdown automata exists for the following language?
I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
- 329