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

Line 10: Line 10:
 
! <math>L(G_1) \cap L(G_2) = \phi</math>
 
! <math>L(G_1) \cap L(G_2) = \phi</math>
 
|-
 
|-
−
|Regular
+
|Regular Grammar
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
 
|-
 
|-
−
|DCFG
+
|Det. Context Free
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{No}}
+
| {{UD}}
 
| {{?}}
 
| {{?}}
−
| {{No}}
+
| {{UD}}
 
|-
 
|-
−
|Complement
+
|Context Free
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{No}}
+
| {{UD}}
 
|-
 
|-
−
|Concatenation
+
|Context Sensitive
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
 
|-
 
|-
−
|Kleene star
+
|Recursive
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
|-
 
−
|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}}
 
 
|-
 
|-
 +
|Recursively Enumerable
 +
| {{D}}
 +
| {{UD}}
 +
| {{UD}}
 +
| {{UD}}
 +
| {{UD}}
 +
| {{UD}}
 +
 
|}
 
|}

Revision as of 18:06, 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 Grammar D D D D D D
Det. Context Free D D UD UD ? UD
Context Free D D UD UD UD UD
Context Sensitive D UD UD UD UD UD
Recursive D UD UD UD UD UD
Recursively Enumerable D UD UD UD UD UD
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=2644"
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