0

Consider the language

$$L=\{0^n w 1^m \mid \text{where}\; w \text{ belongs to } (a+b)^* , n \text{ is number of } a \text{'s in }w, m \text{ is no of } b\text{'s in }w \text{ and }n>m \}$$

I can surely say that this is not a DCFL but I am not sure about it being CFL or recursive. I have no idea how to proceed.

Can someone please help ?

Hans Hüttel
  • 4,271
Zephyr
  • 1,163
  • 1
  • 15
  • 30

1 Answers1

1

A language $L_1$ is recursive if there exists a Turing machine that accepts every string in $L_1$ and rejects every string not in $L_1$.

Hint: How can you use this to prove that $L$ is recursive?

If $L$ is a context-free language, then there exists a $p \in \mathbb{N}$ such that for every $s \in L$ with $|s| \geq p$ we have that we can write $s = uvwxy$ such that

  1. $|vx| > 0$
  2. $|vwx| \leq p$
  3. For all $i \geq 0$ we have that $uv^iwx^iy \in L$

Hint: How can you use this to show that your $L$* is not context-free?

Hint: Consider $s = 0^{p+1}a^{p+1}b^p1^p$.

Hans Hüttel
  • 4,271
  • You mean $|vwx|\le p$ for the second condition, don't you? – hmakholm left over Monica Sep 07 '17 at 20:15
  • Of course. Fixed now. – Hans Hüttel Sep 07 '17 at 20:23
  • According to pumping lemma, there does not exist any v and x for strings like 0000aaaabbb111 because if we pump v and x then 0's and 1's increase but it will not give proper no of a's and b's and thus doesn't belong to language. So it is not context free. Am I correct? – Zephyr Sep 07 '17 at 20:24
  • You must find a string whose length is at least $p$ and show that no partition of it will satisfy conditions 1-3. In the above you are assuming that $p$ is at most $14$ but we do not know what $p$ is and you are only considering a particular fixed partition. This will not work. Moreover, you are referring to "it" in a way that makes in unclear what you actually mean. – Hans Hüttel Sep 07 '17 at 20:29