New answers tagged

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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar

Top 50 recent answers are included