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(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