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.