Formal language theory notes

```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

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.

```