Completely random selection of possible test questions

  1. For the language L = (01)+
  a) build a DFA which recognizes it.
  b) write the grammar for it
  c) construct the generating TM for it.


  2) Is the property "Does L contain at least two strings?" (for r.e. L's) itself r.e.?

  3) Linear language:  Has a grammar where no production has more than one variable
  on the right hand side (there may be many terminals, but no more than one variable).

  i.e.   A -> abAcd    B -> Ab    C -> ccC   are all valid productions
  but   A -> AA       B -> AB    C -> aaAbbBccC are not.

  The pumping lemma for linear languages (notation z = uvwxy) states that for |z| bigger
  than the pumping constant, |vx| > 0 and |uvxy| <= n, it must be the case that uv^iwx^iy
  (for any i >= 0) must be in L as well.

  Show that the language L = { a^ib^ia^ib^i | i > 0}  is not linear.


  4) Find a linear grammar for the language L = { a^ib^i | i > 0}


  5) Prove the following identity for regexps:  (r*)* = r*
    n.b. this will probably require two inductions; one in each direction.    

  6) Build a TM to recognize the following language:

    L = { ww | w in (0+1)* }

  7) Find a CFG with no useless symbols equivalent to :

    S -> AB | CA
    B -> BC | AB
    A -> a
    C -> aB | b

  8) Show that the following language is not CF:
      
    L = { a^ib^jc^k | i < j < k }