New answers tagged pushdown-automata
0
votes
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
L={x#y ∣ x, y ∈ {0,1}* ∧ x≠y}
See, To approach this, we can have followiing ...
0
votes
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
I want to give you some intuition why your language isn't CFL. We know that every CFL there exist atleast one PDA. If PDA doesn't exist that means languages definitely not CFL. So I give you intuitive ...
- 468
1
vote
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
Idea
The pumping lemma for context-free languages is not useful since M is "pumpable" with pumping length $p=2$. Instead, we will select a word in $\mathcal M$ that has less number of $a$'s ...
- 34.1k
0
votes
in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?
Your image comes from M.Li and P.M.B. Vitányi: Kolmogorov Complexity and its Applications, Chapter 4 in Handbook of Theoretical Computer Science, vol. A, J. van Leeuwen Editor.
Both conjectures ...
- 27.6k
0
votes
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
This is incorrect -- it does not take into account that $|vwx|$ can have more than $p$ characters. I will try to salvage it in the coming days.
Ogden's lemma seems to work better here. Suppose $L$ is ...
- 136
0
votes
Accepted
in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?
$K{-}DPDA$ is equivalent to $2{-}DPDA$ for any $K \geq3. $That means for example $2{-}DPDA$ is capable of do the same work as $3{-}DPDA$ do, $2{-}DPDA$ is capable of do the same work as $4{-}DPDA$ ...
- 468
2
votes
Accepted
Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
Your language is DCFL. But you made NPDA because in state $q_5$ the transitions $(q_5,\epsilon,a)\neq\emptyset$ and $(q_5,\epsilon,A)\neq\emptyset$ made your diagram NPDA as I previously said. Below ...
- 468
2
votes
Accepted
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
Your language is NCFL. Your design of NPDA is perfectly right. And in state $q_0,q_1$ and $q_2$ transitions makes your diagram NPDA. You accepts your strings by final state that is $q_3.$ If you want ...
- 468
1
vote
Accepted
Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $
First of all your language is CFL means NCFL not DCFL because machine has push confusion. Therefore DPDA design is not possible. Only NPDA has power to accept your language.
You have to understand ...
- 468
1
vote
Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$
First of all your language is DCFL so there exist at least one DPDA for your language but you made NPDA because at state $q_0$ ,$\delta(q_0,0,A)\neq\emptyset$ and $\delta(q_0,\epsilon,A)\neq\emptyset$ ...
- 468
Top 50 recent answers are included