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
0answers
37 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
50 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\...
-2
votes
0answers
42 views

Looking to learn more about Counter automaton?

I have to write a paper for my class about counter automaton, their usage, their impact, and more. and I'm stuck finding good resources to learn about these strange anomalies :). I was wondering if ...
0
votes
1answer
28 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
23 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 (...
-1
votes
0answers
20 views

How to create a (N)PDA for L={w∈{a,b}⋆ |w=(a2b)n mitn∈N0}?

I just can't get any further on this task. How should I create a cellar machine for this language? The word is asymmetrical for n = 1 and has a character length of 3. So the cellar will never be empty ...
0
votes
1answer
22 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
43 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
31 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
20 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
27 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
11 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
37 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
14 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
23 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
39 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
29 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
17 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
26 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
24 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
55 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
59 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
29 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
31 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
22 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
11 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 ...
3
votes
3answers
84 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
vote
0answers
79 views

Question about proof of Lemma 2.41 - Sipser book

Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ...
0
votes
1answer
35 views

Formal definition of a language accepted by PDA

I am a bit confused on how to give a formal definition of the language accepted by A? I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" ...
-2
votes
1answer
34 views

PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$ S \to [S] \mid \{S\} \mid \Lambda $$ How can I develop a pushdown automaton for this language?
0
votes
1answer
40 views

PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$

I'm pretty new to the PDA topic. How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$ I've tried all the possibilities, but I still somehow end up accepting all words.
0
votes
1answer
74 views

How to convert NPDA to PDA?

I have been given this Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be ...
-1
votes
1answer
115 views

How do I convert this PDA to CFG?

How do I convert this PDA to CFG? I am currently stuck with this, any help would be appreciated, thank you in advance!
0
votes
1answer
35 views

The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
2
votes
1answer
107 views

Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
0
votes
2answers
45 views

Is it decidable for a NPDA to halt?

I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string. But are there ...
1
vote
0answers
25 views

A pda that accepts all strings over an alphabet

If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is L={w | w belongs to (a,b,c,d)*} How would that be constructed? My idea is to have one state as ...
1
vote
0answers
38 views

How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation) a PDA goes on to compare ...
2
votes
1answer
36 views

How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?

After defining pushdown automaton in Sipser's book at p. 113: at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following: My question is about the part "...
0
votes
2answers
74 views

In a NPDA if the stack is empty, where the start/end state are the same can you go again

Thoughts I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ...
-1
votes
1answer
27 views

Find CFG for the following language

I need to show that the following language is context free: $$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}$$
1
vote
0answers
113 views

Determine the language of the given NPDA

Thoughts I am wondering is the language $ab^*$, since $a$ pushes $X$ to the stack and $b$ pops, and if there is an $a$ there has to be a $b$ to get back to the final state? Also, is it right to say $...
0
votes
0answers
46 views

Constructing a PDA which acceptsL {${a^i b^j c^k}$| $i,j,k≥0$ and $i=j$ or $i=k$}

I have to construct a PDA which accepts the L {${a^i b^j c^k}$| $i,j,k≥0$ and $i=j$ or $i=k$} I cannot quite graph how to handle the 'or' To make it easier for myself, I constructed strings where $i=...
0
votes
2answers
56 views

For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)

Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0} I’m trying to design a PDA. My aproach is: -for every 2 ‘a’ push an ‘a’ -for every 4 ‘c’ push a ‘c’ -then pop them ...
4
votes
1answer
135 views

Prove or disprove {wtw^R | |w| = |t|} is context free

The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$ It looks like the language can be "pumped" by context free pumping lemma, ...
0
votes
2answers
44 views

Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

My assignment asks Let $S = \{ w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star ; (∃i < k) w_i\neq w_{i + 1}^r$ , i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
0
votes
1answer
86 views

Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?

I recently found a question asking whether the language given below is context-free or not: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$ My intuition is that I can design a non-deterministic push-down ...
1
vote
1answer
33 views

Developing a Context Free Grammar whilst knowing the number of terminals

I am trying to develop a CFG for the language $L$ defined by: $L = \{a^{n+2}bba^{n-2} | n > 1\}$ The problem I am having is that I cannot develop the CFG for this language no matter what I try. ...
0
votes
1answer
64 views

Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}

I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option. NPDA are not very intuitive to me. The only solution I found online is: I don‘t ...
0
votes
1answer
92 views

Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code: ...

1
2 3 4 5
9