Theory: Difference between revisions
| Line 12: | Line 12: | ||
===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ||
* Type 2 of the [[Chomsky Hierarchy]], a proper superset of | * Type 2 of the [[Chomsky Hierarchy]], a proper superset of RLs | ||
* Recognized by nondeterministic pushdown automata | * Recognized by nondeterministic pushdown automata | ||
** Deterministic pushdown automata cannot recognize all | ** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)! | ||
* Closed under union, concatenation, Kleene, reverse | * Closed under union, concatenation, Kleene, reverse | ||
* Not closed under complement or difference | * Not closed under complement or difference | ||
| Line 21: | Line 21: | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
* LR(''n'') (Knuth, 1965): | * 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 | ||