# Questions tagged [pushdown-automata]

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

508 questions
Filter by
Sorted by
Tagged with
12 views

### CFG to DPDA Conversion explanation?

S → a[S] |S+S| b I have basically such a grammatik which needs to be converted into DPDA. I have the solution but I dont really understand how it is being done.Can anyone explain it to me? S→aQS′R|bR ...
1 vote
133 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, ...
• 241
108 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) ? ...
72 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
60 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
45 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
58 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
281 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 ...
• 11
16 views

### Can you a push multiple symbols on simplified PDA stack in one transition?

I encountered this problem when I was converting a PDA to a CNF and I was looking for two transitions that push and pop the same symbol(one pushes and one pops). The PDA I was converting had this ...
• 61
1 vote
53 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 ...
1 vote
61 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 ...
199 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 ...
84 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 ...
1 vote
70 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
37 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-...
• 456
1 vote
62 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 ...
• 161
1 vote
128 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 ...
1 vote
53 views

### Determine the language of the NPDA

I have to write the language of the below $NPDA$(Non-Deterministic Push Down Automata). I think that from $q_0$ to $q_1$ and then $q_2$, we are actually building the below all the strings of $0$'s ...
1 vote
103 views

### Why DFA's configuration space is finite and PDA configuration space is infinite?

I read from this post the term configuration space. I don't know the meaning of configuration space. What is the exactly meaning of configuration space? And why DFA's configuration space is finite ...
22 views

### Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate]

The question is from my homework: Is the language $\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$ a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ...
39 views

### Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n

It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
• 1
15 views

### Can anyone here recommend me some Constructing PDA problems?

The type of problems I am trying to practice is cobstructing a pda that will help me learn a lot. I need some tricky questions not the easy straightforward ones. Like L=a^mb^na^nb^m m+n=n+m Or using 2 ...
1 vote
43 views

• 133
1 vote
62 views

### If the Pushdown-Automaton for a language is deterministic, is the language non-ambiguous?

For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the ...
51 views

### Proof no DPDA can accept Palindrome (need explanation for the attached proof)

The given proof for proving that no DPDA can be constructed to accept palindromes is unclear. There exists another similar question but it only explains the proof partially. I understood how it aims ...
• 1
145 views

### Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free

Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free. Hi I'...
1 vote
62 views

### Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?

Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
123 views

### Construct PDA for $\{a^ib^j\ | i > j \ \& \ i < 2j\}$ [duplicate]

How to construct PDA for language $\{a^ib^j\ | i > j \ \& \ i < 2j\}$? I know how to check first and second conditions separately but at once there's a problem.
269 views

### PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$

I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$ I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character ...
• 135
29 views

### PDAs with bounded stacks accept regular languages [duplicate]

I've been trying to solve the following problem from Martin's Introduction to languages and the theory of computation, 4th edition: Suppose that $L \subset \Sigma^{*}$ is accepted by a PDA $M$. ...
75 views

### DPDA by empty stack

Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just ...
71 views

### How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
1 vote
44 views

### Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$

Construct a PDA, which recognizes the following language $L$: $L = \{w\;|\; |w|_a > 2|w|_b\}$, so it is the language that consists of words which have more than twice as many $a$'s as $b$'s. I ...
• 111
39 views

### What kind of words does this PDA accepts

I have a PDA A = ({q0, q1}, Σ = {a, b}, Γ = {a}, δ, F = {q1}), with these transition functions δ: ((q0,a,ε),(q0,a)); ((q0,b,ε),(q0,a)); ((q0,a,ε),(q1,ε)); ((q1,a,a),(q1,ε)); ((q1,b,a),(q1,ε)). The ...
• 3
1 vote
52 views

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &... • 15 1 vote 1 answer 133 views ### How can I combine 2 PDA's into 1 PDA deterministically? I have two PDAs one with$\{a^i b^j \mid i > j\}$and the other$\{a^i b^j \mid i < j\}$. I know how to combine these two PDAs non-deterministically. My question is how do I combine these two ... • 11 0 votes 0 answers 94 views ### How to convert PDA to CFG and make a state diagram I'm trying to understand this but I can't figure out how to proceed, I have an initial procedure but I don't know if it's right, could someone give me examples of how to do this? My attempt S→q0 Z q2 →... 0 votes 1 answer 56 views ### Difference between Counter-machine and stack machine I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ... 0 votes 1 answer 80 views ### Why finiteness problem of CFL is decidable? We know that every$CFL$has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space? 1 vote 1 answer 109 views ### Why equality is decidable for regular language but not for$CFL?$There are infinitely many different$PDAs$for the same$CFL$exist, therefore we can't check equality for$CFL.$But also there are infinitely many different$DFA$exists for same regular language. ... 1 vote 1 answer 112 views ### How does Sipser's 0n1n PDA reject 0101? In Sipser's Theory of Comp in 2.2 the following PDA is provided for${\{0^n1^n|n\ge0}\}$. I follow how to process "", ... 2 votes 2 answers 149 views ### Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not$? $I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language$L$is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always$w$as$\epsilon$and$x$∈$(a+b)^∗$. But my ... 0 votes 1 answer 71 views ### The same transition twice in Pushdown automata (PDA) If we want to design a PDA that accepts all words those the first half equals reverse of the second half and there is a '#' between them, "ab#ba" for example. We start push each letter we ... -1 votes 1 answer 51 views ### I can't get the commands? each of which includes$~\$~$ instead of $~\epsilon~$ of the pushdown automaton

The pushdown automaton is given as the below diagram. What I know are as below. $$1,0 ~\texttt{->}~ \epsilon_{} ~~ \leftarrow~~ \text{As 1 is inputted then 0 will be popped from the stack}$$ \$...