Difference between revisions of "Grammar: Decidable and Undecidable Problems"

Line 3: Line 3:
 
|-
 
|-
 
! Grammar
 
! Grammar
−
! <math>w \in L(M)</math>
+
! <math>w \in L(G)</math>
−
! <math>L(M) = \phi</math>
+
! <math>L(G) = \phi</math>
−
! <math>L = \Sigma^*</math>
+
! <math>L(G) = \Sigma^*</math>
−
! <math>L(M_1) \subseteq L(M_2)</math>
+
! <math>L(G_1) \subseteq L(G_2)</math>
−
! <math>L(M_1) = L(M_2)</math>
+
! <math>L(G_1) = L(G_2)</math>
−
! <math>L(M_1) \cap L(M_2) = \phi</math>
+
! <math>L(G_1) \cap L(G_2) = \phi</math>
 
|-
 
|-
−
|Union
+
|Regular
 +
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
−
| {{No}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 18: Line 18:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|Intersection
+
|DCFG
 +
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
+
| {{?}}
−
| {{Yes}}
+
| {{No}}
−
| {{Yes}}
 
 
|-
 
|-
 
|Complement
 
|Complement

Revision as of 18:01, 26 February 2014

Grammar: Decidable and Undecidable Problems
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
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=2641"
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 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