Fall 98, CSE 468: Solution of Final exam

Exercise 1

  1. L1 is context-free. A CF grammar which generates L1 is:
    S -> AB1 | B2C
    A -> aA | lambda
    B1 -> bB1c | lambda
    C -> cC | lambda
    B2 -> aB2b | lambda
  2. L2 is context-free. A CF grammar which generates L2 is:
    S -> AC
    A -> aAb | lambda
    C -> bCc | lambda
  3. L3 is not context-free. Given a natural number n, consider the string anb2ncn and show that contradicts the pumping lemma.

Exercise 2

A deterministic CF grammar equivalent to the given one is:
S -> AB
A -> bAC | lambda
B -> lambda | aB
C -> c | d
From this grammar we can easily construct the deterministic PDA. Informally, the PDA will accept a sequence of b's and put them on the stack, then will accept a sequence of c's and d's, alternated arbitrarily, and pop all the b's from the stack. When the stack is empty, will accept a sequence of a's.

Exercise 3

Informally, the TM will repeat the following steps:
  1. scan the tape from left to right (skipping the x's and the y's) until you find an a or a b. Change it to x. If no a or b are found, then halt (accept).
  2. continue scanning from left to right until you find a b (if in (1) you found an a) or an a (if in (1) you found a b). Change it to y.
  3. go back on the tape from left to right (skipping the y's) until you find an x. Go to point (1).

Exercise 4

Let us denote by "Even" the set of strings on Sigma of even length.
  1. L1 is not RE. In fact, the property
    p1(L) = Even is contained in L
    is not finitely reachable (Even is infinite). Then by the theorem of Rice-Shapiro L1 is not RE.

  2. L2 is RE. In fact, we can semidecide that e(M) belongs to L2: one way is to generate all the strings of even length, and try them "in parallel" on the machine M. As soon as one of them is accepted by M (if any), we halt and accept e(M).
    However, L2 is not Rec. To prove this, note that the the property
    p2(L) = the intersection between Even and L is not empty
    is not trivial. In fact, p2({aa}) holds and p2({}) does not hold. Hence by the theorem of Rice L2 is not Rec.
    Another way to prove that L2 is not Rec is by observing that L3 is not RE (see next point).

  3. L3 is not RE. To prove this, note that the property
    p3(L) = the intersection between Even and L is empty
    is not upward-closed. In fact, p3({}) holds and p3({aa}) does not hold. Then by the theorem of Rice-Shapiro L3 is not RE.

  4. L4 is Rec. In fact, given a string x, we can decide whether x belongs to L4 by checking that x is in the right format (i.e. that x is the encoding of a TM) and that x has even length. Note that the theorems of Rice and of Rice-shapiro do not apply here, since L4 is described by an intentional property of machines, not an extensional one.