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
24 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 ...
-3
votes
0answers
25 views

CFLs are accepted by two-state PDAs w/o $\epsilon$-transitions

Show that if $L$ is accepted by a PDA, then $L$ is accepted by a PDA having at most two states and no $\epsilon$-transitions.
-1
votes
0answers
19 views

Counter automata for languages with conditions on the numbers of 0s and 1s [closed]

A counter automation is a PDA with just two stack variables, $A$ and $Z$, for which the string on the stack is always of the form $A^n Z$ for some $n≥0$. For some CFLs, such as $\{0^i 1^i \mid i≥0\}$, ...
0
votes
1answer
31 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
2answers
48 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 ...
0
votes
0answers
42 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.
1
vote
1answer
46 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 ...
-2
votes
0answers
29 views

Is $\{ww^Ra^{|w|}\mid w\in\{a,b\}^*\}$ context-Free? [duplicate]

How can I prove that this language is context free and construct a pda recognizing it? $L = \{ww^Ra^{|w|}\mid w\in\{a,b\}^*\}$
0
votes
0answers
26 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$. ...
0
votes
1answer
24 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 ...
0
votes
1answer
47 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
1answer
33 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 ...
0
votes
1answer
36 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 ...
1
vote
2answers
48 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 &...
1
vote
1answer
65 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 ...
0
votes
0answers
36 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
1answer
42 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
1answer
46 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
1answer
66 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
1answer
68 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
2answers
127 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
1answer
39 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
1answer
50 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} $$ $...
0
votes
1answer
38 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 ...
0
votes
1answer
37 views

Poping a symbol on a PDA when Input and Stack are Irrelevant

Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
1
vote
2answers
47 views

Deterministic Pushdown Automata that accepts #a = #b

I am trying to create a DPDA that accepts words from the following Language: $$ L = \{wx \; | \;w \in \{a,b\}^*, \#a = \#b \} $$ My intuition was to initially put an $x$ on the stack and then write an ...
0
votes
1answer
25 views

Prove that grammar accepting arithmetic expressions is not regular

I created a grammar which accepts all arithmetic expressions consisting of $+,-,*,/, (, )$. I created the following grammar: $S \rightarrow M+-M$ $+-M \rightarrow +M+-M$ $+-M \rightarrow -M+-M$ $+-M \...
0
votes
0answers
40 views

DPDA for $\{0^{m+n} 1^n \mid m \geq 0, n \geq 0\}$

I need to construct a deterministic PDA for the language $\{ 0^{m+n} 1^n \mid m \geq 0, n \geq 0 \}$. So we want all words consisting of $0$'s followed $1$'s such that there are never more $1$'s than $...
0
votes
0answers
37 views

pushdown automata question

We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
0
votes
1answer
53 views

How to show that pda accepts empty language?

I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski ...
0
votes
1answer
36 views

Pushdown automaton with binary stack

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language ...
1
vote
0answers
33 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
1
vote
1answer
44 views

PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
0
votes
1answer
36 views

PDA accepting of a specific symmetric language

Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$. if we have $a$ This side of the string, on the other side of the string we have $aa$. and if we have $b$ This side of the ...
0
votes
1answer
49 views

Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$

How can I construct a PDA which accepts the language $\{a^i b^j c^k \mid k\geq \min(i,j)\}$ I think about different solutions such as building a stack with two-state. one state is for $i < j$ and ...
0
votes
0answers
62 views

Is this PDA correct for L = {0^m1^n | n ≤ m ≤ 2n}?

I have drawn this transition diagram for the given language. Is this correct?
0
votes
1answer
23 views

PushDown Automata

Let Sigma = {a,b,c} and let L be the language of all words in which all the a’s come before the b’s and there are the same number of a’s as b’s and arbitrarily many c’s that can be in front, behind, ...
2
votes
1answer
60 views

Proof that class of languages accepted by DPDA by empty stack is not closed under union

My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property): $$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
0
votes
1answer
143 views

CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s

I'm trying to find the CFG and PDA for the above language. I have so far come up with this $S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$ However, I realized that this is just a subset of the ...
0
votes
0answers
39 views

Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

I'm trying to find the PDA of the above language. I understand that this is the complement of the language $L_1=\{w : w=a^nb^n : n\geq0\}$ However, I can't understand the idea behind constructing the ...
-1
votes
1answer
65 views

PDA for $\{a^ib^jc^k \mid (i+j) \bmod 3 = 0, k = i + j\}$

Construct a pushdown automaton that accepts $$\{a^ib^jc^k \mid (i+j)\bmod 3 = 0, k = i + j\}$$
-1
votes
1answer
45 views

PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }

I have seen this similar question but I can't seem to apply the same technique for the equation $7j = 5i + 6k$
2
votes
1answer
61 views

Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try: I know that context-free languages are closed under union operation. Also I know how to make a PDA for ...
3
votes
2answers
146 views

Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
-2
votes
1answer
42 views

Turing machine without return equivalent to Finite Automaton, PushDown Automaton or Turing Machine?

I have seen that a Turing machine without return is a Turing machine $M$ which at each stage of its calculation systematically moves its read / write head to the right.The aim of the exercise is to ...
1
vote
0answers
47 views

Different PDA design processes -- both valid?

This video shows how to design PDA from a CFG: https://www.youtube.com/watch?v=ZImtQBMSW_Y Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
2
votes
2answers
185 views

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements. $\quad\quad\text{I. }L$ is deterministic context-free. $\quad\quad\text{II. }L$ is context-...
1
vote
2answers
59 views

PDA accepting all words not of the form $b^na^n$

I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages. If I have context-free ...
1
vote
1answer
28 views

Unix glob() function and formal language equivalence

Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, ...
1
vote
1answer
29 views

Can a Turing machine or Push Down Automaton construct languages of type 3?

I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a ...

1
2 3 4 5
10