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

Line 9: Line 9:
 
! <math>L(G_1) = L(G_2)</math>
 
! <math>L(G_1) = L(G_2)</math>
 
! <math>L(G_1) \cap L(G_2) = \phi</math>
 
! <math>L(G_1) \cap L(G_2) = \phi</math>
 +
! <math>L(G_1) is finite</math>
 
|-
 
|-
 
|Regular Grammar
 
|Regular Grammar
 +
| {{D}}
 
| {{D}}
 
| {{D}}
 
| {{D}}
 
| {{D}}
Line 25: Line 27:
 
| {{?}}
 
| {{?}}
 
| {{UD}}
 
| {{UD}}
 +
| {{D}}
 
|-
 
|-
 
|Context Free
 
|Context Free
Line 33: Line 36:
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 +
| {{D}}
 
|-
 
|-
 
|Context Sensitive  
 
|Context Sensitive  
 
| {{D}}
 
| {{D}}
 +
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
Line 44: Line 49:
 
|Recursive
 
|Recursive
 
| {{D}}
 
| {{D}}
 +
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
Line 57: Line 63:
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
 
| {{UD}}
−
 
+
| {{UD}}
 
|}
 
|}

Revision as of 18:20, 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> <math>L(G_1) is finite</math>
Regular Grammar D D D D D D D
Det. Context Free D D D UD ? UD D
Context Free D D UD UD UD UD D
Context Sensitive D UD UD UD UD UD UD
Recursive D UD UD UD UD UD UD
Recursively Enumerable D UD UD UD UD UD UD
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=2649"
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 D 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