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
25 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
46 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} $$ $...
-1
votes
0answers
96 views

Draw a deterministic push down automaton

Can anyone make Dpda for the following languages $L_1=\{ a^nb^m \mid n\neq m,n,m>0\}$ I have find too little solution and but everyone violating Dpda definition like for any $q\in Q ,x\in T$ (...
0
votes
1answer
28 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
30 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 ...
6
votes
0answers
214 views

From coin flips to algebraic functions via pushdown automata

Given a coin with a probability of heads of $\lambda$, sample the probability $f(\lambda)$. This is the Bernoulli factory problem, and it can be solved only for certain functions $f$. (For example, ...
1
vote
2answers
37 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
21 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
31 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
36 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
43 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
23 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
31 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
35 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
35 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
33 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
18 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
20 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
46 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
40 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
30 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
25 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
38 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
52 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
80 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
27 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
42 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
170 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
49 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
22 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
23 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
vote
1answer
52 views

Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are ...
1
vote
1answer
33 views

Reduce PDA for a given language

I drew a Push-down Automata, accepting the following language: $$ \{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}. $$ Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with ...
1
vote
1answer
55 views

PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$. I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if ...
2
votes
1answer
57 views

Where to put the state in a two-stack push down automaton?

theoretically, the state is between the two kleene-stars of the work-alphabet gamma* q gamma* where q is the current state and each ...
2
votes
1answer
52 views

Can PDA have empty stack transition?

From a youtube video, this PDA can recognize any palindrom. However, from wikipedia, here is one of the criteria of PDAs. We clearly see that the transition function can't take an empty stack as ...
1
vote
1answer
36 views

Some questions regarding methods for solving pushdown automata problems

I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one: For example, take this language: $\...
0
votes
0answers
32 views

What is the most commonly used/ most practical method to parse context sensitive languages?

what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean Not too theoretical but in opposite to that, with practical usecases Not too complicated (...
1
vote
1answer
67 views

Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

According to this statement: Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular ...
0
votes
1answer
108 views

Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format

As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following However, as ...
1
vote
1answer
61 views

Two way deterministic pushdown automaton accepting word consisting of two equal words

I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language: {ww | w ∈ {a, b}*} Does anyone have any idea? Thanks a lot
0
votes
1answer
37 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
1answer
44 views

What is the computational class of a pushdown automaton with real values?

Say there is a push-down automata, in this example I'll use a deadfish-like set: +: increase x by 1 0: set x to 0 ...
0
votes
1answer
109 views

Create a PDA that accepts the following language

I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for ...
0
votes
1answer
270 views

{a^n b^n c^n | n>=1} - PDA

I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive. How I attempted it ...
3
votes
0answers
60 views

bounding the height of stack when checking acceptance pushdown automaton

Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form. There exists a constant $c$, computable from $A$, such that: if $w$...
0
votes
1answer
264 views

Decidability of PDA

I have following problem: INFPDA={⟨A⟩ |A is PDA and L(A)=infinite language} Prove that this is decidable problem. So my idea how to solve this problem is the ...
1
vote
1answer
88 views

Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG). I suspect that languages like $\text{L} = \{...
0
votes
0answers
25 views

Is there only one unique DPDA that accepts a specific language?

Or is it possible to construct more than one DPDA that accepts exactly the same language?
0
votes
0answers
21 views

Constructing a Push Down Automaton

Given a 7 tuple push down automaton M = (K, Σ, Γ, Δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, Γ = {a}, s = p, and F = {r}, with the transitions ((p, b, ε), (q, ε)), ((q, a, e,), (p, a)), ((p, c, a), (...

1
2 3 4 5
10