Theory

Formal Languages

Regular Languages (Class REG)

• Type 3 of the Chomsky Hierarchy
• Recognized by finite state machines
• Closed under union, concatenation, Kleene, intersection, difference, complement, reverse

Context-Free Languages (CFLs) / Grammars (CFGs)

• Type 2 of the Chomsky Hierarchy, a proper superset of RL's
• Recognized by nondeterministic pushdown automata
  • Deterministic pushdown automata cannot recognize all CFL's!
• Closed under union, concatenation, Kleene, reverse
• Not closed under complement or difference
• The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
• LL(n):
• LR(n):

Context-Sensitive Languages

• Type 1 of the Chomsky Hierarchy, a proper superset of CFL's
• Recognized by linear bounded automata

Recursively-Enumerable Languages (Class RE)

• Type 0 of the Chomsky Hierarchy, a proper superset of CSL's
• Recognized by Turing Machines