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
vote
1answer
21 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
votes
0answers
21 views

PDA for $ S \to S0S1S0S \mid S0S0S1S \mid S1S0S0S \mid \epsilon $

How do I design a pushdown automaton for the language described by the following grammar? $$ S \to S0S1S0S \mid S0S0S1S \mid S1S0S0S \mid \epsilon $$ I tried converting the grammar to CNF, but didn't ...
1
vote
1answer
24 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
30 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
26 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
53 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
30 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
33 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
29 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
55 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
69 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 ...
0
votes
1answer
49 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
25 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
39 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
52 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
108 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
58 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
93 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
26 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
20 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
20 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
52 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
52 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
25 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
87 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
50 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
234 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
50 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
31 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
56 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
59 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
55 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
81 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
77 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
18 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
vote
1answer
66 views

Is this push-down automaton non-deterministic, as JFLAP states?

There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism. In this example it is detecting non-determinism in state ...
0
votes
0answers
50 views

Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
0
votes
0answers
33 views

Context free grammar to Chomsky normal form

I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form: S $\rightarrow$ aSX | B B $\rightarrow$ bBX | ε X $\rightarrow$ a | b I have a solution S $\...
-1
votes
1answer
54 views

Create a PDA for the given language

The task is to create a PDA for this language. The |u| a reffers to the number of a's in that word. I have tried working on it as two separate languages that I can later combine, but I fail to even do ...
0
votes
0answers
32 views

How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)? [duplicate]

I have a following grammar: S -> aSa | bSb | $\lambda$. And I have to figure out whether the language produced by this grammar is recognizable by DPDA. I can't find any theorems about it. Obviously, ...
0
votes
0answers
32 views

Can a pushdown automaton solve the halting problem for another Pushdown automaton?

Can a pushdown automaton solve the halting problem for another Pushdown automaton? It's already shown here turing machine can solve the halting problem for a pushdown automaton. Decidability of ...
0
votes
1answer
30 views

Is there any property about height of PDA?

I'm trying to find a PDA for $L$ which modifies the stack height at most one. $L=\{a^ib^i\mid i\geq 0\}$ I think there is no such PDA but how can I prove it? My attempt is for a given string, find ...
0
votes
1answer
44 views

Solving membership problem for a PDA-generated language without converting the PDA to a CFG

The classic solution for the membership problem of a language generated by a PDA is to convert said PDA to a CFG and then to use CYK or a similar algorithm. I was wondering if there are any known ...
0
votes
0answers
73 views

context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...
2
votes
1answer
114 views

When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
-1
votes
1answer
34 views

How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
-1
votes
1answer
61 views

Construct a PDA that recognizes the following language: L={uawb: u,w ∈ {a,b}*, |u|=|w|}

I am having trouble finding the PDA with 1 state for this one. So far my solution is this but i cant figure out how to get to 1 state. Alphabet: {a, b}, Stack alphabet (the first symbol is the ...
0
votes
2answers
38 views

PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
0
votes
0answers
19 views

Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]

Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
4
votes
3answers
93 views

$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language

Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as $$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ ...

1
2 3 4 5
9