Check out my first novel, midnight's simulacra!

Theory: Difference between revisions

From dankwiki
No edit summary
No edit summary
Line 1: Line 1:
==Formal Languages==
==Formal Languages==
===Regular Languages===
* 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''):
* LL(''n''):
* LR(''n''):
* LR(''n''):
===Context-Free Languages (CFLs) / Grammars (CFGs)===
===Context-Sensitive Languages===
* Type 1 of the Chomsky Hierarchy, a proper superset of CFL's
* Recognized by linear bounded automata
===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])===
* Type 0 of the Chomsky Hierarchy, a proper superset of CSL's
* Recognized by Turing Machines


[[Category: CS GRE Prep]]
[[Category: CS GRE Prep]]

Revision as of 09:44, 7 September 2009

Formal Languages

Regular Languages

  • 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