# Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

539 questions
Filter by
Sorted by
Tagged with
1 vote
129 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 ...
121 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" ...
349 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?
138 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.
843 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 ...
2k 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!
260 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 ...
225 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 ...
1 vote
282 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
190 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
147 views

### How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...
473 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 "...
971 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 ...
31 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
427 views

1 vote
184 views

### Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question) ...
1k views

### Pushdown Automata - can you have multiple transition functions options between 2 states?

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states? For example, ...
58 views

### DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$with$|y|_1 \le k$and$k \in \mathbb N: k\ge1$}\}$

I need some help with the following task: I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$with$|y|_1 \le k$and$k \in \mathbb N: k\ge1$}\}$. How can I recognize that the new ...
2k views

### Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s This is a homework question,...
1 vote
78 views

### What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?

Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code. ...
3k views

### Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language: $L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$ The concatenation of two mutually ...
1k views

### A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
1 vote
395 views

### It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
1 vote
2k views

### L(M)=L where M is a TM that can move right or stay, so L is decidable

Suppose that L(M)=L where M is a one tape TM that can move right or stay. I need to Show that L is decidable. I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
212 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 In fact the languages of one counter machines are accepted by deterministic PDA's although the proof is ...
1 vote