Interlude -Example 3.4: `

MATH

$\QTR{Large}{A}$ is not a CFL.

choose MATH large enough so that , by the CFL pumping lemma,

Moreover,

Let MATH and MATH MATH $\QTR{Large}{=}$ MATH , some MATH , for all $\QTR{Large}{i}$. However this is not possible since

MATH , a constant and MATH . In particular the sequence MATH, is not constant.

____________________________________________________________

Approach:

If j=0 then "reject"; If j=1 then "accept";

if j is even then divide by two; if j is odd and >1 then "reject".

Repeat if necessary.

____________________________________________________________

Description:

  1. Check if $\QTR{Large}{j=0}$ or $\QTR{Large}{1}$ . If $\QTR{Large}{j=0}$ reject. If $\QTR{Large}{j=1}$ accept.

  2. Check, by going left to right if the string has even or odd number of zeros

  3. If odd then "reject"

  4. If even then go back left, erasing half the zeros.

  5. goto 1.

__________________________________________________________

Pseudo-code: