$L=\{0^m1^n \mid3m\leq 2n\}$ via pumping lemma

57 Views Asked by At

Hi I’m trying to prove that L isn’t regular $L=\{0^m1^n \mid3m\leq2n\}.$

It’s from an exam of CS class, that’s my solution even if at some point I’m stuck.

  1. I assume that L is regular
  2. Let k > 0 length of the pumpling lemma
  3. Let w = $0^{2k/3}1^k$ ∈ L and |w| = $2k/3 + k > k$ ‘cause I must respect the condition that $3m≤2n$; $m≤2k/3$
  4. Let xyz be a subdivision of w such that $|xy|<k$ and $ y \neq ε$
  5. ‘Cause of that x and y are not completely contained in the first sequence of zeros

We have to divide in two cases:

(a) xy contains only zeros

  1. Let z = $0^{(2k/3)-p-q}1^k$ with p >= 0 and q > 0 (cause y can’t be an empty string whereas x yes)
  2. xyz = $0^p0^q0^{(2k/3)-p-q}1^k$
  3. We can choose i = 2 so $xy^{2}z=0^p0^{2q}0^{(2k/3)-p-q}1^k$ and $xy^2z=0^{(2k/3)+q}1^k$
  4. This string ∉ L for $q>k/3$

(b) xy contains both zeros and ones

And now I’m stuck … I don’t know if I overthink for case (a) but for case (b) I’ve no clue