Theory: Difference between revisions
| Line 15: | Line 15: | ||
* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | * Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | ||
* Rewrite rule: A→γ, where A is a non-terminal, and γ is a string of terminals and non-terminals | * Rewrite rule: A→γ, where A is a non-terminal, and γ is a string of terminals and non-terminals | ||
* Recognized by nondeterministic pushdown automata | * Recognized by nondeterministic pushdown automata (NPDAs) | ||
** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)! | ** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)! | ||
* Closed under union, concatenation, Kleene, reverse | * Closed under union, concatenation, Kleene, reverse | ||