Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for Second Examination Fall 2005

• There could be a problem similar to any given homework problem. (But I am aware that we have only 75 minutes for the whole test. So I won't give one that can't be worked in that amount of time.)
• There will be some true/false questions.
• There will be some fill-in-blanks questions.
• Be able to correctly state the pumping lemma for context-free languages.
• There could be a problem like our homework on the CYK algorithm.
• There could be a question like: "Describe, in English, the language accepted by the TM diagrammed here:" Of course, I would only give a very easy example, because even the easiest examples require careful examination.
  Another such question would be, "The TM diagrammed here computes a function. Define that function in English."
• Understand each of the following:
  • derivation of a string
  • parser
  • ambiguous grammar
  • grammar which respects semantics (meaning)
  • Turing machine
  • recursive function
  • undecidability (what it really means)
  • NTM
  • recursively enumerable
  • diagonal language
  • configuration (also called instantaneous description) of a machine
  • computation of a Turing Machine (sequence of configurations)
• What is the Church-Turing Thesis? Why is it important?
• I could ask you to draw pictures and write words (not give a formal proof) to explain something like:
  • How a multi-tape or multi-track TM can be emulated by a TM.
  • Why there is a TM which accepts that same language as a given NTM.
• There will not be a long proof of the test. Here is a short proof:
  Prove that if a language is decidable it can be enumerated in canonical order by some machine.
  (At most half a page.)
• Which of the following problems (languages) are undecidable?
  • The Halting Problem
  • Given two context-free grammars, do they generate the same language?
  • Given one context-free grammar G and one string w, does G generate w?
  • Given a loop of string, can it be untangled?
• Some hard T/F questions. True or False:
  • The complement of a context-free language is context-free.
  • The complement of a decidable language is decidable.
  • The complement of a recursively enumerable language is recursively enumerable.