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)