Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
385
questions
26
votes
3answers
1k 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 ...
4
votes
1answer
221 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 ...
2
votes
5answers
11k views
Explaining why a grammar is not LL(1)
I need some help with explaining why a grammar is not LL(1).
Let us take the following grammar:
$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
...
1
vote
1answer
57 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 ...
1
vote
2answers
58 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 ...
3
votes
1answer
55 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, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
1
vote
0answers
49 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 ...
2
votes
1answer
90 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 ...
3
votes
1answer
46 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 ...
1
vote
4answers
50k views
Difference between DPDA and NPDA?
What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA. ...
0
votes
0answers
45 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|\}$, ...
0
votes
0answers
31 views
About Specification of PDA
I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $,
$Q$ is a finite set of states
$\Sigma$ is a finite set of input symbols (input alphabet)
$\Gamma$ is a finite ...
4
votes
0answers
90 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
votes
1answer
194 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?
1
vote
2answers
5k views
Does a PDA immediately accept if at final state with empty stack?
If computation on a PDA reaches a final state with an empty stack, will it immediately accept, regardless of whether or not the input tape has ended. For example if I have a PDA to recognize the ...
1
vote
1answer
119 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 ...
2
votes
0answers
39 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
0answers
25 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 ...
16
votes
1answer
3k views
Is it decidable whether a pushdown automaton recognizes a given regular language?
The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable ...
0
votes
1answer
22 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 ...
0
votes
0answers
65 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}^{...
-1
votes
1answer
66 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.
2
votes
1answer
155 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 ...
1
vote
1answer
72 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 ...
1
vote
1answer
501 views
Context free grammar for $bin(n)bin(n+1)^R$
It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.
Here, at 1.b, is a PDA which ...
0
votes
1answer
140 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-...
2
votes
2answers
838 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 ...
1
vote
1answer
51 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 ...
2
votes
0answers
1k 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 ...
1
vote
1answer
48 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 ...
1
vote
1answer
236 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$:
$\...
0
votes
1answer
691 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}$}
...
1
vote
1answer
49 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 ...
0
votes
1answer
138 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
1answer
249 views
CFG problem solved with PDA - looking for alternative solution
I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$
and what I have done so far is to make PDA which simply does the following:
If on the ...
6
votes
1answer
312 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
50 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
1answer
97 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
74 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
240 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
48 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
128 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 ...
6
votes
3answers
10k 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
1k 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
230 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 ...
1
vote
3answers
2k 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
152 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
691 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
81 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
448 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 ...
