Regarding questions that were raised in class last week:

1.  Names for levels in the Chomsky hierarchy

  Formally, the Chomsky hierarchy is as follows:

  Type 0: General rewriting system (recursively enumerable languages)

    Rules of the form
    X -> Y    

    X rewrites to Y where X and Y are any strings of nonterminals 
    and/or terminal symbols.

  Type 1: Context-sensitive rewriting system (context sensitive languages)

    Rules of the form
    A ->  Y / alpha ____ beta

    A rewrites to Y where A is a single nonterminal; Y, alpha, and beta
    are a strings (with Y nonempty) of nonterminals and/or terminal symbols;
    and the rule means that in a derivation step rewriting A to Y,
    alpha must appear to the left of A and beta to its right.  

  Type 2: Context-free rewriting system (context-free languages)

    Rules of the form
    A -> Y

    A rewrites to Y where A is a single nonterminal, and Y is a string
    of nonempty nonterminals and/or terminal symbols.  (Any CFG
    that rewrites a nonterminal to the empty symbol can be converted
    to one that does not.)

  Type 3: Finite-state rewriting system (regular languages)

    X -> a Y
    X -> a

    X, a nonterminal, rewrites to the string "a Y" where a is a 
    terminal symbol and Y is a nonterminal (possibly equal to X).


2. Differences between levels in the Chomsky hierarchy

  The language {a^n b c^m : n,m >= 1} is a Type 3 (regular) language.

  The language {a^n b^n : n >= 1} is a Type 2 (context-free) language,
  but is not a regular language.

  The language {a^n b^n c^n : n >= 1} is a Type 1 (context-sensitive) 
  language, but not context-free.

  The following appeared on an earlier version
  of this page, but is not correct:

    The language {a^n : n is a prime number} is a Type 0 language,
    but is not a context-sensitive language.

  My thanks to Dr. P. K. Jha for pointing this out.
  


3. Equivalence of NDFA's and DFA's.

  I have photocopied a textbook example of the conversion from a
  nondeterministic FSA to a DFA that accepts the same language, and will
  make it available in class.