Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

Filter by
Sorted by
Tagged with
0
votes
1answer
23 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,...
0
votes
0answers
23 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. ...
3
votes
3answers
407 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 ...
4
votes
1answer
84 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 ...
1
vote
1answer
30 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
42 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
35 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
25 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 ...
1
vote
1answer
64 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
28 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 ...
0
votes
0answers
34 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
14 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 ...
2
votes
0answers
68 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
105 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
0answers
140 views

a^nb^nc^nd^n 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 ...
1
vote
1answer
76 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
34 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 ...
0
votes
0answers
34 views

Proving the Complement of a DCFL is DCFL [duplicate]

If I Have a DCFL $L$ ( a CFL which can be recognised by a DPDA ), How do I prove that $\overline{L}$ is also a DCFL I checked my textbook for a proof but I wasn't able to understand the language. Can ...
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 ...
0
votes
1answer
21 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
44 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
vote
1answer
59 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
votes
1answer
64 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.
0
votes
1answer
81 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-...
1
vote
1answer
27 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
721 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
88 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$: $\...
2
votes
1answer
81 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 ...
0
votes
1answer
214 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
42 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 ...
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 ...
0
votes
1answer
91 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\}$?
0
votes
1answer
64 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 ...
6
votes
1answer
181 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
47 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^*...
1
vote
1answer
64 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 ...
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
72 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 ...
0
votes
1answer
154 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 ...
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 ...
2
votes
1answer
72 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
3answers
504 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 ...
0
votes
0answers
43 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
1answer
105 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
1answer
69 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
1answer
65 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
293 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
2answers
79 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$...
1
vote
1answer
430 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 ...