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
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.
Return to the course home page.