# 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
1k views

### PDA for this context-free grammar

I have the following CFG $G$: \begin{align} S &\rightarrow aAbb \mid aaBb \\ A &\rightarrow aAbb \mid \epsilon \\ B &\rightarrow aaBb \mid \epsilon \\ \end{align} I have to create a ...
• 141
4k views

### prove no DPDA accepts language of even-lengthed palindromes

How do you prove that the language of even-lengthed palindromes, i.e., $L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton? Is ...
• 991
2k views

### Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Is the following language context free? $$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\}$$ As pointed out by sdcvvc, a word in this language can also be ...
• 747
4k views

### Converting CFG to PDA

I have the following CFG, $S \rightarrow CB$ $C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$ $B \rightarrow AB \text{ }|\text{ } \varepsilon$ $A \rightarrow a\text{ }|\text{ }b$ ...
3k views

### Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \}$ context free?

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \}$ context free ? If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \}$ is ...
• 747
3k views

### Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question. The question states that the PDA has at most 2 states. Clearly 1 will ...
• 163
1k views

### Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?

Is the language $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ? I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
• 747
3k views

### Cartesian construction of PDA and DFA

How would I go about using Cartesian construction to find the intersection between a PDA and a DFA? Is there another term for Cartesian construction? Would it be similar to the procedure for finding ...
• 207
27k views

### Convert CFG to PDA

Is there any set of rules or methods to convert any context free grammar to a push down automata? I already found some slides online but I wasn't able to understand them. In slide 10 he speaks ...
• 227
1k views

16k views

### Constructing PDA for $a^{2n} b^{3n}$

So I have been given the task of creating an PDA that recognises the language $\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$. Am I right in thinking that it needs to have at least 3 times number of $b$'s ...
• 141
11k views

### Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }
• 665
15k views

### Push down automata for $\{a^n b^n c^n | n \ge 0\}$

I am learning about context free languages. I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's. Intuitively however it seems that a ...
20k views

### Explaining why a grammar is not LL(1)

I need some help with explaining why a grammar is not LL(1). Let us take the following grammar:  \begin{align} S \rightarrow & aB \mid bA \mid \varepsilon \\ A \rightarrow & aS \mid bAA \\ ...
• 576
1k views

### Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
• 576
5k views

### why are deterministic PDAs not closed under concatenation?

I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one. But can someone prove this ...
• 1,269
11k views

• 31
4k views

### How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable ...
• 1,587
2k views

### Constructing deterministic PDA for not regular language

Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many c’...
1 vote
3k views

### When generating a PDA from a CFG do I have a receiving state?

Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
46k 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,077
5k views

### Context-free grammar to a pushdown automaton

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
• 225
1k views

### Eliminating useless productions resulting from PDA to CFG converison

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions ...
• 461
947 views

### How to prove that ε-loops are not necessary in PDAs?

In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a ...
• 72k
4k views

### Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa) There may also exist a Deterministic Pushdown ...
3k views

### Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
• 893
3k views

### If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}$ (i.e. the right quotient) is context-...
• 201
6k views

### How does a two-way pushdown automaton work?

Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape. I recently had the question of determining the computational power ...
• 435
25k views

### Are Turing machines more powerful than pushdown automata?

I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
• 2,193
6k views

### Are there inherently ambiguous and deterministic context-free languages?

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language ...
• 12.8k
801 views

### Converting a context free grammar to a PDA -- is my solution correct?

I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG: \$\qquad\begin{align} S &\to R1R1R1 \\ R &\to ...

1
7 8 9 10
11