Check out my first novel, midnight's simulacra!
Theory: Difference between revisions
From dankwiki
No edit summary |
|||
| Line 11: | Line 11: | ||
* Not closed under complement or difference | * Not closed under complement or difference | ||
* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | * The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | ||
* LL(''n''): | ====Efficiently-Parsed CFLs==== | ||
* LR(''n''): | * LL(''n'') (Lewis and Stearns, 1968): | ||
* LR(''n'') (Knuth, 1965): | |||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the Chomsky Hierarchy, a proper superset of CFL's | * Type 1 of the Chomsky Hierarchy, a proper superset of CFL's | ||
Revision as of 10:23, 7 September 2009
Formal Languages
Regular Languages (Class REG)
- Type 3 of the Chomsky Hierarchy
- Recognized by finite state machines. Equivalent to DSPACE(1).
- 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
Efficiently-Parsed CFLs
- LL(n) (Lewis and Stearns, 1968):
- LR(n) (Knuth, 1965):
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
