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
-1 votes
0 answers
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 ...
user avatar
  • 1
1 vote
3 answers
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, ...
user avatar
  • 241
2 votes
2 answers
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) ? ...
user avatar
-1 votes
1 answer
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 ...
user avatar
  • 155
1 vote
1 answer
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 ...
user avatar
  • 155
0 votes
1 answer
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 ...
user avatar
  • 155
0 votes
1 answer
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 ...
user avatar
  • 155
0 votes
1 answer
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 ...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
  • 61
1 vote
2 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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}) ...
user avatar
  • 13
0 votes
1 answer
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-...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 161
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 1
2 votes
0 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
43 views

Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language

I was solving some exercises about CFL from past years' homework and faced this question. Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
user avatar
0 votes
0 answers
50 views

Constructing a PDA for the language of words $uv$ such that $2|u| = 3|v|$

Consider the language $\{ w=uv : 2|u|=3|v|, u,v \in \{a,b\}^+ \}$. How to compare the lengths of the words? How to know where is the end of $u$ and the beginning of $v$? What algorithm is used for ...
user avatar
  • 1
-4 votes
1 answer
105 views

Creating a PDA that accepts the following language

Using automata-lib 5.0.0 (Python library), I need help creating a Python program that simulates a PDA that only accepts the following language: L = {a^m b^n | 0 ≤ m != n} If you could provide any ...
user avatar
2 votes
1 answer
159 views

Useless states in a PDA

I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads: 4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
user avatar
  • 123
0 votes
1 answer
28 views

Why do non Context Free languages need more stacks?

In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.” We haven’t delved into CS and reclusively enumerable languages much ...
user avatar
  • 217
1 vote
1 answer
138 views

Why is $a^mb^nc^pd^q$ with $m+p=n+q$ context-free?

$L = \{$$a^mb^nc^pd^q \mid m+p = n+q,$$\text{ where } m, n, p, q \geqslant0\}$ If, for instance, we try to construct a PDA for a similar language $L2 = \{$$a^mb^nc^pd^q \mid m=p $ $\text{and}$ $ n=q,$$...
user avatar
  • 133
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 1
0 votes
1 answer
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'...
user avatar
1 vote
2 answers
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 ...
user avatar
0 votes
0 answers
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.
user avatar
2 votes
1 answer
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 ...
user avatar
  • 135
0 votes
0 answers
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$. ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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$...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 111
0 votes
1 answer
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 ...
user avatar
  • 3
1 vote
2 answers
52 views

PDA with multiple element access - $i$ - access PDA

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 &...
user avatar
  • 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 ...
user avatar
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 →...
user avatar
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 ...
user avatar
  • 1
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?
user avatar
  • 1
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. ...
user avatar
  • 1
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 "", ...
user avatar
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 ...
user avatar
  • 1
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 ...
user avatar
-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} $$ $...
user avatar
0 votes
1 answer
54 views

Convert a PDA with transition for a state to itself to another PDA

Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this? EDIT (My thoughts): I guess we can ...
user avatar

1
2 3 4 5
11