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=== | ===Regular Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#reg REG])=== | ||
* Type 3 of the Chomsky Hierarchy | * Type 3 of the Chomsky Hierarchy | ||
* Recognized by finite state machines | * Recognized by finite state machines | ||
Revision as of 09:44, 7 September 2009
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
