Theory: Difference between revisions
No edit summary |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 32: | Line 32: | ||
* Rewrite rule: αAβ→αγβ, where A is a non-terminal, and {α, β, γ} are strings of terminals and non-terminals | * Rewrite rule: αAβ→αγβ, where A is a non-terminal, and {α, β, γ} are strings of terminals and non-terminals | ||
* Recognized by linear bounded automata | * Recognized by linear bounded automata | ||
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | |||
* Decided by [[Turing Machines]] | |||
===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])=== | ===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])=== | ||
* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs | * Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs | ||
* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals | * Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals | ||
* Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | * Recognized <i>but not decided</i> by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | ||
== | |||
==Closures== | |||
{|class="wikitable borders" | |||
! class !! concat !! union !! intersection !! kleene !! setdiff !! complement | |||
|- | |||
| REG || Y || Y || Y || Y || Y || Y | |||
|- | |||
| CFL || Y || Y || n || Y || n || n | |||
|- | |||
| R || Y || Y || Y || Y || Y || Y | |||
|- | |||
| RE || Y || Y || Y || Y || n || n | |||
|- | |||
|} | |||
[[Category: CS GRE Prep]] | [[Category: CS GRE Prep]] | ||