# Tag Info

### 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 ...

### 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

### 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

### 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 ...
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
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
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