Summaries of Grammars/Languages
of various types, 0,1,2, and
3
|
Type 0 (RE
Sets), Unrestricted, or Phrase-Structured |
Type 1,
Context Sensitive |
Type2,
Context Free |
Type3,
Regular |
Acceptors |
Turing
Machines (Det. Or Nondet.), SIMPLE
Language Programs |
NLBA
(DLBA?) |
NPDA (Not
DPDA) |
DFSA
(NFSA) |
Determinism= Non-determinism? |
YES |
NOT SURE
YET |
NO |
YES |
Closed
under |
Union ,
Intersection, Concatenation, Closures, and
Substitution |
Union,
Intersection, Complementation,
Concatenation, Substitution,
and Positive Closure |
Union,
Concatenation, Substitution and Closures (Ref. and
Positive) |
Union,
Intersection, Comp., Substitution, Concatenation, and Closures (Ref. and
Positive) |
Unsolvable
Problems |
Halting,
Membership, Finiteness, Infiniteness, Emptiness, Equality,
Subset |
Equality,
Subset, Ambiguity, Totality, Infiniteness, and
Emptiness |
Equality,
Subset, Ambiguity, Totality, Intersection Emptiness, Complement CF,
Regular, and DCFLness |
Almost
none |
Solvable
Problems |
Step (x,y,t): Predicate to decide if program y stops upon
taking an input x in t or fewer steps (Time limit
imposed) |
Membership |
Membership,
Emptiness, Infiniteness |
Ambiguity,
Membership, Emptiness, Totality, Infiniteness, Equality, Subset, and Minimality |
Applications (Good
Reference: Automata,
Computability and Complexity, by Elaine
Rich, 1st ed., Prentice Hall
Publishing) |
Computer
Programming, System Security verification system (TM’s Halting Problem),
and Problem Reduction of Halting Problem to other Unsolvable
problems. |
Specification
of CF Attribute grammars (in
eliminating attributes) |
Compiler
Design (Parser), Unambiguous Language design tool, CFG used in RNA
Secondary Structure prediction system, CFG used for Reverse Engineering,
CFG used in specifying most syntax features of practical programming
languages. |
Compiler
design (Scanner), ALU Adder/Multiplier design, Network
Communications Protocol (non-halting FSA for TCP), Protein Motifs specifier (Regular Exps),
DFSA used in BLAST (DNA Sequence query
engine) |