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
5 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
15 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
0answers
9 views

PDA for complement of a^n b^n [duplicate]

I'm trying to figure out a PDA of L', where L = {a^n b^n | n>=0}. However, when I'm trying to find it, I can only do so for {a^i b^j | i, j>=0}, when the complement does not contain only that. ...
-1
votes
1answer
12 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
0answers
12 views

What would be an accepting sequence of configurations for this PDA?

What would be an accepting sequence of configurations for this PDA? I'm not sure how to approach this question, unless it's just trial and error?
-1
votes
1answer
36 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
43 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 ...
2
votes
2answers
49 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 ...
-6
votes
0answers
100 views

PDA and context-free languages

How can we prove that: Class of linear bounded PDA languages ∼ Class of CFLs I know that for a linear bounded PDA there is a constant $k$ such that the stack size for $w$ is at most $k|w|$. I also ...
-4
votes
0answers
18 views

Can this be recognized by a PDA? [duplicate]

Can {a^(n) b^(n) c^(n) | n > 0} be regognized by a Push-Down-Automata?
-2
votes
1answer
24 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
votes
0answers
35 views

Construct the PDA for the language [duplicate]

Construct the PDA for the language $L =\{a^i b^j c^k, j=2i \text{ or } j=2k \text{ and }i,j,k\geq0\}$
1
vote
0answers
38 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 ...
3
votes
2answers
163 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
48 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
21 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
37 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
31 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
36 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
56 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
33 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
31 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
66 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
80 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
55 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
32 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
40 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
86 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
189 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
59 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
196 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
43 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
21 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), (...
2
votes
3answers
58 views

How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
1answer
70 views

Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$ I have tried to find a pushdown automata and it turned out to be a ...
1
vote
3answers
37 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
0
votes
2answers
102 views

How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
0
votes
0answers
51 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
1answer
316 views

Converting PDA to CFG

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
0
votes
1answer
70 views

PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
0
votes
1answer
32 views

Is it possible to form a PDA for this language?

$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$ Is this even context free? I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (...
0
votes
1answer
69 views

How can I combine 2 PDA's into 1

I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ...
0
votes
0answers
71 views

Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
0
votes
2answers
63 views

Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
-1
votes
1answer
112 views

Formal definition of non deterministic PDA

How would you convert the following formal definition of deterministic pushdown automata into non deterministic ? Deterministic PDAs In general terms, a deterministic PDA is one in which there is at ...
-1
votes
1answer
97 views

Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
0
votes
1answer
19 views

checking configuration history of Turing machine using PDA

I am trying to understand the technique of using configuration history in proofs. To prove that: $\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$ given $<M,w>$ we ...

1
2 3 4 5
10