Midterm Exam Name: _____________________________

CSC 8150-001 Theory of Computing
Wednesdays from 6:15pm to 8:45pm in Mendel 260
Dr. David Matuszek, Mendel 162C, (610) 519-5654

If you scored 70 or less on the midterm exam, you may do this as a take-home exam. Your grade will be averaged with the regular midterm grade. It is not required that you do this exam. (Questions about Turing are part of this make-up exam, so don't skip them.) Due November 3.

Read me or else!
The language L contains strings of a's and b's. The a's occur only in even numbers: aa, aaaa, aaaaaa, etc.. The empty string does belong to the language. Hence, the language is: {empty, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, aaaab, aabaa, aabbb, baaaa, bbbbb, baabb, bbbaa, ...}.
  1. Write a regular expression for the language L.


  2. Draw a deterministic finite-state automaton to recognize language L. Leave out the trap state.






  3. Write a right-linear grammar to recognize language L. Remember to specify all four parts of the language.









  4. Using your grammar from the previous question, write a derivation for the string baabb.



  5. Write a context free grammar that is not regular to recognize language L. Remember to specify all four parts of the language.







  6. Using your context free grammar from the previous question, draw a derivation tree for the string baabb.






  7. Formally specify all the parts of a Turing machine to recognize language L except for the transition table (that's the next question!).








  8. Assuming the parts in the previous question, write (or "program") a Turing machine to recognize language L (The table probably has more rows than you need to use.).
    Current state Symbol read Symbol written Direction Next state
  9. Formally specify all the parts of an NPDA to recognize language L except for the transition table (that's the next question!).






  10. Assuming the parts in the previous question, write (or "program") a pushdown automaton to recognize language L. (The table probably has more rows than you need to use.).
    State Input symbol Top of stack Push Next states
             
             
             
             
             
             
             
             
             
             
             
             
  11. Formally specify a grammar to recognize -L, that is, the complement of L.









  12. Tell what kind of grammar (regular, context free, context sensitive, or recursively enumerable) you wrote for the previous question.


  13. Draw a machine to recognize -L.








  14. Tell what kind of machine you wrote for the previous question.


    15. [End of questions about language L.]

  15. Tell what the following symbols stand for. (Because it is difficult to create Web pages with Greek letters, some of the symbols are specified in English words.)

    1. Capital sigma

    2. Capital gamma

    3. Q

    4. Lowercase delta

    5. Lowercase epsilon or lambda

    6. Capital sigma with a star

    7. Curly braces, { }

    8. Vertical bars around a string:  |w|