Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 3: | Line 3: | ||
|- | |- | ||
! Grammar | ! Grammar | ||
− | ! <math>w \in L( | + | ! <math>w \in L(G)</math> |
− | ! <math>L( | + | ! <math>L(G) = \phi</math> |
− | ! <math>L = \Sigma^*</math> | + | ! <math>L(G) = \Sigma^*</math> |
− | ! <math>L( | + | ! <math>L(G_1) \subseteq L(G_2)</math> |
− | ! <math>L( | + | ! <math>L(G_1) = L(G_2)</math> |
− | ! <math>L( | + | ! <math>L(G_1) \cap L(G_2) = \phi</math> |
|- | |- | ||
− | | | + | |Regular |
+ | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
− | |||
| {{Yes}} | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
Line 18: | Line 18: | ||
| {{Yes}} | | {{Yes}} | ||
|- | |- | ||
− | | | + | |DCFG |
+ | | {{Yes}} | ||
| {{Yes}} | | {{Yes}} | ||
| {{No}} | | {{No}} | ||
| {{No}} | | {{No}} | ||
− | | {{ | + | | {{?}} |
− | | {{ | + | | {{No}} |
− | |||
|- | |- | ||
|Complement | |Complement |
Grammar | <math>w \in L(G)</math> | <math>L(G) = \phi</math> | <math>L(G) = \Sigma^*</math> | <math>L(G_1) \subseteq L(G_2)</math> | <math>L(G_1) = L(G_2)</math> | <math>L(G_1) \cap L(G_2) = \phi</math> |
---|---|---|---|---|---|---|
Regular | Yes | Yes | Yes | Yes | Yes | Yes |
DCFG | Yes | Yes | No | No | ? | No |
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 |