Theory: Difference between revisions

Revision as of 09:44, 7 September 2009

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

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):

@@ Line 1: / Line 1: @@
 ==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-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]]