Arjun Suresh (talk | contribs) (Created page with ":{| class="wikitable" |+ align="top"|Closure properties of language families |- ! Operation ! Regular ! DCFL ! CFL ! CSL ! Recursive ! RE |- |Union | {{Yes}} | {{No}} | {{Yes}...") |
Arjun Suresh (talk | contribs) |
||
Line 1: | Line 1: | ||
:{| class="wikitable" | :{| class="wikitable" | ||
− | |+ align="top"| | + | |+ align="top"|Grammar: Decidable and Undecidable Problems |
|- | |- | ||
− | ! | + | ! Grammar |
− | ! | + | ! <math>w \in L(M)</math> |
− | ! | + | ! <math>L(M) = \phi</math> |
− | ! | + | ! <math>L = \Sigma^*</math> |
− | ! | + | ! <math>L(M_1) \subseteq L(M_2)</math> |
− | ! | + | ! <math>L(M_1) = L(M_2)</math> |
− | ! | + | ! <math>L(M_1) \cap L(M_2) = \phi</math> |
|- | |- | ||
|Union | |Union |
Grammar | <math>w \in L(M)</math> | <math>L(M) = \phi</math> | <math>L = \Sigma^*</math> | <math>L(M_1) \subseteq L(M_2)</math> | <math>L(M_1) = L(M_2)</math> | <math>L(M_1) \cap L(M_2) = \phi</math> |
---|---|---|---|---|---|---|
Union | Yes | No | Yes | Yes | Yes | Yes |
Intersection | Yes | No | No | Yes | Yes | Yes |
Complement | Yes | Yes | No | Yes | Yes | No |
Concatenation | Yes | No | Yes | Yes | Yes | Yes |
Kleene star | Yes | No | Yes | Yes | Yes | Yes |
Homomorphism | Yes | No | Yes | No | No | Yes |
<math>\epsilon</math>-free Homomorphism | Yes | No | Yes | Yes | Yes | Yes |
Substitution (<math>\epsilon</math>-free) | Yes | No | Yes | Yes | No | Yes |
Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes |
Reverse | Yes | No | Yes | Yes | Yes | Yes |
Grammar | <math>w \in L(M)</math> | <math>L(M) = \phi</math> | <math>L = \Sigma^*</math> | <math>L(M_1) \subseteq L(M_2)</math> | <math>L(M_1) = L(M_2)</math> | <math>L(M_1) \cap L(M_2) = \phi</math> |
---|---|---|---|---|---|---|
Union | Yes | No | Yes | Yes | Yes | Yes |
Intersection | Yes | No | No | Yes | Yes | Yes |
Complement | Yes | Yes | No | Yes | Yes | No |
Concatenation | Yes | No | Yes | Yes | Yes | Yes |
Kleene star | Yes | No | Yes | Yes | Yes | Yes |
Homomorphism | Yes | No | Yes | No | No | Yes |
<math>\epsilon</math>-free Homomorphism | Yes | No | Yes | Yes | Yes | Yes |
Substitution (<math>\epsilon</math>-free) | Yes | No | Yes | Yes | No | Yes |
Inverse Homomorphism | Yes | Yes | Yes | Yes | Yes | Yes |
Reverse | Yes | No | Yes | Yes | Yes | Yes |