(For arbitrary CFGs G, G1 and G2 and an arbitrary regular set R)
(For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R)
Line 83: Line 83:
 
But whether <math>L(G) \subseteq L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)
 
But whether <math>L(G) \subseteq L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)
  
===For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R===
+
===For arbitrary DCFGs G, G1 and G2 and an arbitrary regular expression R===
 
The following problems are '''decidable''':
 
The following problems are '''decidable''':
  
 
# Whether <math>(L(G1))^\complement</math> is a DCFL? (trivial)
 
# Whether <math>(L(G1))^\complement</math> is a DCFL? (trivial)
# Whether <math>L(G) = R</math>?
+
# Whether <math>L(G) = L(R)</math>?
# Whether <math>L(G) \subseteq R</math>?
+
# Whether <math>L(G) \subseteq (R)</math>?
# Whether <math>R \subseteq L(G)</math>?
+
# Whether <math>L(R) \subseteq L(G)</math>?
 
# Whether <math>L(G)</math> is a CFL? (trivial)
 
# Whether <math>L(G)</math> is a CFL? (trivial)
  

Revision as of 20:45, 27 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)</math> is finite
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 UD UD UD UD UD UD UD

Checking if <math>L(CFG)</math> is finite is decidable because we just need to see if <math>L(CFG)</math> contains any string with length between <math>n</math> and <math>2n-1</math>, where <math>n</math> is the pumping lemma constant. If so, <math>L(CFG)</math> is infinite otherwise its finite.

Other Undecidable Problems

For arbitrary CFGs G, G1 and G2 and an arbitrary regular expression R

The following problems are undecidable:

  1. Whether <math>(L(G1))^\complement</math> is a CFL?
  2. Whether <math>L(G1) \cap L(G2)</math> is a CFL?
  3. Whether <math>L(G1) \cap L(G2)</math> is empty?
  4. Whether <math>L(G) = L(R)</math>?
  5. Whether <math>L(R) \subseteq L(G)</math>?
  6. Whether <math>G</math> is ambiguous?
  7. Whether <math>L(G)</math> is a DCFL?

But whether <math>L(G) \subseteq L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)

For arbitrary DCFGs G, G1 and G2 and an arbitrary regular expression R

The following problems are decidable:

  1. Whether <math>(L(G1))^\complement</math> is a DCFL? (trivial)
  2. Whether <math>L(G) = L(R)</math>?
  3. Whether <math>L(G) \subseteq (R)</math>?
  4. Whether <math>L(R) \subseteq L(G)</math>?
  5. Whether <math>L(G)</math> is a CFL? (trivial)





blog comments powered by Disqus
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)</math> is finite
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 UD UD UD UD UD UD UD

Checking if <math>L(CFG)</math> is finite is decidable because we just need to see if <math>L(CFG)</math> contains any string with length between <math>n</math> and <math>2n-1</math>, where <math>n</math> is the pumping lemma constant. If so, <math>L(CFG)</math> is infinite otherwise its finite.

Other Undecidable Problems[edit]

For arbitrary CFGs G, G1 and G2 and an arbitrary regular expression R[edit]

The following problems are undecidable:

  1. Whether <math>(L(G1))^\complement</math> is a CFL?
  2. Whether <math>L(G1) \cap L(G2)</math> is a CFL?
  3. Whether <math>L(G1) \cap L(G2)</math> is empty?
  4. Whether <math>L(G) = L(R)</math>?
  5. Whether <math>L(R) \subseteq L(G)</math>?
  6. Whether <math>G</math> is ambiguous?
  7. Whether <math>L(G)</math> is a DCFL?

But whether <math>L(G) \subseteq L(R)</math> is decidable. (We can test if <math>L(G) \cap compl(L(R))</math> is <math>\phi</math>)

For arbitrary DCFGs G, G1 and G2 and an arbitrary regular set R[edit]

The following problems are decidable:

  1. Whether <math>(L(G1))^\complement</math> is a DCFL? (trivial)
  2. Whether <math>L(G) = R</math>?
  3. Whether <math>L(G) \subseteq R</math>?
  4. Whether <math>R \subseteq L(G)</math>?
  5. Whether <math>L(G)</math> is a CFL? (trivial)





blog comments powered by Disqus