Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
356
questions
6
votes
1answer
198 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 ...
1
vote
1answer
48 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^*...
0
votes
0answers
33 views
What is abstract machine for parallel multiple context free grammar (PMCFG)?
It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
0
votes
1answer
74 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
vote
1answer
46 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 ...
0
votes
1answer
160 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
1answer
47 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 ...
2
votes
1answer
73 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 ...
5
votes
3answers
9k 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 ...
-1
votes
3answers
598 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 ...
1
vote
1answer
117 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 ...
0
votes
0answers
44 views
Building deterministic pushdown automaton for given grammar
I am trying to build a DPDA for the given grammar:
$S \to aR$
$R \to bRT \ |\ \varepsilon$
$T \to cSR \ |\ \varepsilon$
I tried simplifying grammar first (removing null and unit productions, ...
1
vote
3answers
1k views
Push two symbols to stack at once in a push down automata
I am pretty new to PDAs and I was solving a problem which asked to design a PDA for the following: $a^n b^{2n}$.
The transitions on the PDAs I've encountered so far have pushed only one symbol onto ...
0
votes
1answer
74 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 ...
1
vote
2answers
592 views
How is CFL-reachability solvable in exponential time and space?
I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. ...
1
vote
1answer
66 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 ...
1
vote
1answer
298 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 ...
1
vote
1answer
446 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
...
2
votes
0answers
86 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 ...
0
votes
1answer
164 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?
2
votes
2answers
160 views
Is the language with decreasing numbers of a, b and c context-free by pumping lemma?
So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.
$$L=\{w:w\in(a+b+c)^*, n_a(...
-1
votes
1answer
138 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 ...
2
votes
0answers
82 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 ...
3
votes
1answer
236 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 ...
1
vote
0answers
12 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 ...
2
votes
1answer
49 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 ^...
2
votes
3answers
441 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 ...
1
vote
1answer
134 views
Nondeterministic PDA for the following language with Kleene star
I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:
$$L = (aaa^*bab)$$
My normal approach to ...
3
votes
3answers
10k views
Push down automata for $\{a^n b^n c^n | n \ge 0\}$
I am learning about context free languages.
I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's.
Intuitively however it seems that a ...
-1
votes
1answer
152 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
1answer
124 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 ...
1
vote
1answer
27 views
Minimum number of letters
I have an assignment that I have to do and the question is
Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}.
Im not looking for the answer but rather some direction. I ...
7
votes
2answers
225 views
Is this language a Deterministic CFL? $L = \{ a^n (a+b)^n | n>0\}$
$L = \{ a^n (a+b)^n | n>0\}$
a book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
1
vote
1answer
179 views
Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$
My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the ...
2
votes
2answers
95 views
Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]
Given a language $L$ over $\Sigma=\{a,b\}$ let us define
$L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$
Prove: if $L$ is regular, then $L'$ is a context free language.
I know how to ...
1
vote
2answers
45 views
CFG where u has same number of 1s as v [closed]
$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$
Here is my attempt solution, but it is not completely correct, any hint is appreciated
...
2
votes
0answers
33 views
Can pushdown automata be without epsilon transitions? [duplicate]
Are pushdown automata without $\varepsilon$-transitions as powerful as those with them? Intuitively, if we need to make such a transition, we could just add the letters on the next transition we take, ...
2
votes
0answers
169 views
Simulating a turing machine with DPDA with two stacks
In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...
3
votes
1answer
513 views
Equivalence of PDA and a counting PDA
Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size.
Formally, let's define the transition relation as
$\Delta:Q\times (\Sigma \cup \{ \...
0
votes
2answers
773 views
Making a CFG for a^i b^j c^k such that i+j = 3k
I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG.
I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue....
1
vote
1answer
224 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 ...
1
vote
1answer
46 views
Simulate $n$-PDA with $n-1$-PDA
I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure ...
0
votes
0answers
60 views
Where is proof that palindrom language is nondeterministic? [duplicate]
It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but ...
0
votes
0answers
71 views
Can we skip an input in push down automata
Hi here I'm giving a language
L3={0^m 1^(n ) 2^m | m,n ∈ N}
I designed this stack machine in order to accept this given language.
Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
2
votes
1answer
323 views
Understanding context free grammars in conjunction with PDA
I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really ...
2
votes
2answers
807 views
Which of the following languages is accepted by this Pushdown Automaton?
This is a question from a past paper. I am struggling to get my head around the concept of a PDA. I understand that it is a Finite Automaton with a stack but am stuck as far as answering questions ...
0
votes
1answer
132 views
Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $
So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ }
is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL
i even know the grammar for it ...
0
votes
0answers
75 views
Simulate deterministic PDA with 1-tape Turing machine?
Is it possible to write a 1-tape Turing machine in order to simulate a deterministic PDA? How would this be done?
1
vote
1answer
118 views
Does a DPDA halt on all inputs?
Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable?
The standard halting problem is "Given a DPDA and an input $x$, determine ...
-2
votes
2answers
156 views
How do I create a pushdown automata for a language where some characters occur in times in multiples of 2 or 3
I have an assignment to create a pushdown automata for $L=\{a^{3n} c^m b^{2n} \mid n,m\geq 0, m\!\mod\! 2=0\}$ and I am confused how to handle $2n$ and $3n$.
