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
votes
1answer
17 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
25 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
0answers
12 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 ...
1
vote
1answer
30 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
1answer
9 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 ...
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
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
35 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
1answer
22 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
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
15 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
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
54 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 ...
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.
-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 ...
3
votes
2answers
24k views

How to convert PDA to CFG

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CFG for the automata My attempt: $S=A_{03}$ because $...
-1
votes
1answer
28 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
1answer
51 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 ...
0
votes
0answers
10 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
81 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
72 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
32 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" ...
4
votes
1answer
71 views

Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1] In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
0
votes
2answers
70 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 ...
-2
votes
1answer
33 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?
-1
votes
1answer
83 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
34 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
106 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
43 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 ...
2
votes
1answer
75 views

Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
3
votes
3answers
2k views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
1
vote
1answer
159 views

Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
1
vote
0answers
29 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 ...
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 ...
0
votes
1answer
655 views

a^nb^nc^nd^n using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
2
votes
1answer
34 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 "...
-1
votes
1answer
26 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))\}$$
0
votes
2answers
55 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 ...
1
vote
0answers
112 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
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
0answers
42 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=...
46
votes
2answers
31k views

Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
1
vote
2answers
240 views

Does left factoring CFG make it unambiguous?

I came across following problem: If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE? I have many thoughts about this. But I feel they are somewhat ...
0
votes
1answer
83 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. ...
2
votes
3answers
3k views

Why are DCFL not closed under concatenation or Union whereas CFL is?

I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves ...
4
votes
4answers
523 views

Relaxing the stack in a push down automata

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol ...
0
votes
1answer
63 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 ...

1
2 3 4 5
9