View source for Grammar: Decidable and Undecidable Problems ← Grammar: Decidable and Undecidable Problems

:{| class="wikitable"
|+ align="top"|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) 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}}
|}


==Other Undecidable Problems ==

===For CFGs G, G1 and G2 and regular set R===
The following problems are undecidable:

# Whether <math>(L(G1))^\complement</math> is a CFL
# Whether <math>L(G1) \cap L(G2)</math> is a CFL
# Whether <math>L(G1) \cap L(G2)</math> is empty
# Whether <math>L(G1) = R</math>
# Whether <math>G</math> is ambiguous
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) 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