Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
539
questions
3
votes
2
answers
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
8
votes
1
answer
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
26
votes
3
answers
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
2
votes
2
answers
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$
...
3
votes
3
answers
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
6
votes
2
answers
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
8
votes
1
answer
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
2
votes
1
answer
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
9
votes
1
answer
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
2
votes
1
answer
1k
views
Syntax of a Pushdown Automata transition function
I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:
$\delta(q, \lambda, S) = ...
- 298
0
votes
1
answer
5k
views
How to generate a pushdown automata for accepting a language?
I have an exercise in my book to come up with a pushdown automaton accepting a language.
The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings ...
- 325
5
votes
2
answers
17k
views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
- 4,259
2
votes
1
answer
3k
views
Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?
$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $
Is this language a context free language?
If yes give a PDA. If no, give a proof.
The pumping lemma for context free languages doesn't seem to work ...
- 1,269
8
votes
1
answer
330
views
Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$
Clearly, $\text{Deterministic one-counter} \subseteq A$
Is it the case that $ A = \text{Deterministic one-counter}$...
- 1,269
3
votes
1
answer
519
views
Proving that a specific language is a CFL, and that another language is not a CFL
I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:
$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
- 53
2
votes
2
answers
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
3
votes
4
answers
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
3
votes
3
answers
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 ...
- 529
2
votes
6
answers
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
-1
votes
1
answer
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
5
votes
2
answers
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
17
votes
1
answer
11k
views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
- 305
5
votes
1
answer
826
views
Deterministic context-free languages are closed under regular right-product
I am looking for a proof for the following problem:
For languages $L$ and $R$, if $L$ is deterministic context-free
and $R$ is regular, then $LR$ is a deterministic context-free
language.
Note:...
- 354
3
votes
1
answer
3k
views
How can one simulate a PDA with a FIFO queue PDA?
I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
- 83
3
votes
2
answers
5k
views
CFG and PDA for the grammar that has perfectly nested parentheses and brackets
I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.
$\qquad\begin{align}
S &\to [S] \\
S &\to (S) \\
S &\to SS \\
S &\to \varepsilon
\...
- 31
8
votes
2
answers
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
3
votes
3
answers
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’...
user3115
1
vote
2
answers
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.
user10392
51
votes
2
answers
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
3
votes
1
answer
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
2
votes
1
answer
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
11
votes
1
answer
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
24
votes
1
answer
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 ...
- 709
14
votes
2
answers
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
10
votes
3
answers
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
5
votes
1
answer
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
5
votes
6
answers
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
40
votes
2
answers
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
7
votes
1
answer
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 ...
jfisk