Theory: Difference between revisions
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
===Regular Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#reg REG])=== | ===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. Equivalent to [http://qwiki.stanford.edu/wiki/Complexity_Zoo:D#dspace DSPACE(1)]. | ||
* Closed under union, concatenation, Kleene, intersection, difference, complement, reverse | * Closed under union, concatenation, Kleene, intersection, difference, complement, reverse | ||
===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ||