New answers tagged pushdown-automata
1
This is a proof by contradiction. If you're not familiar with proof by contradiction, I suggest learning about that proof method (and more generally, refreshing your knowledge of discrete mathematics and proof techniques) before trying to understand this specific proof.
You can think of it this way: either $M$ exists, or it doesn't. If $M$ does exist, you ...
0
The reverse of a language $L$ is the language $L^R = \{ w^R : w \in L \}$, where $w^R$ is obtained from $w$ by reversing the orders of the letters.
The reverse of a context-free language is context-free. This can be shown by starting with a grammar and reversing all production rules, that is, replacing $A \to \alpha$ by $A \to \alpha^R$. Similarly, the ...
1
Yes, there are. There is an algorithm that, given any PDA $P$ and any input word $x$, directly checks whether $x$ is accepted by $P$, without first converting $P$ to a CFG. The algorithm takes running time $O(n^3)$ (treating the size of $P$ as a constant that is absorbed into the big-O notation).
The idea is that, given a PDA $P$, we can compute a ...
0
Given a pushdown automaton $A = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, define a configuration as a couple $(q, \gamma)$, with $q\in Q$ and $\gamma\in \Gamma^*$. A configuration represents the state $q$ of the PDA, and the stack word $\gamma$.
If there are no $\varepsilon$-transition (and you can always find such a PDA), given a word $u$, you can decide ...
2
Roughly speaking, the PDA consists of two phases.
During the first phase, the PDA reads $a$s. For each $a$ that it reads, it nondeterministically pushes either $A$, or $AA$, or $AAA$ to the stack.
During the second phase, the PDA reads $b$s, popping one $A$ per $b$ read. At the end, the stack needs to be empty.
Details left to you.
Top 50 recent answers are included