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

(→‎Note)
 
(44 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
{{alert|Please don't byheart this table. This is just to check your understanding |alert-danger}}
 +
 
:{| class="wikitable"
 
:{| class="wikitable"
 
|+ align="top"|Grammar: Decidable and Undecidable Problems
 
|+ align="top"|Grammar: Decidable and Undecidable Problems
 
|-
 
|-
 
! 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>
 +
! <math>L(G)</math> is regular?
 +
! $L(G)$ is finite?
 
|-
 
|-
−
|Union
+
|Regular Grammar
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
 +
| {{D}}
 +
| {{D}}
 
|-
 
|-
−
|Intersection
+
|Det. Context Free
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{D}}
−
| {{No}}
+
| {{D}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{UD}}
 +
| {{D}}
 +
| {{D}}
 
|-
 
|-
−
|Complement
+
|Context Free
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{No}}
+
| {{UD}}
 +
| {{UD}}
 +
| {{D}}
 
|-
 
|-
−
|Concatenation
+
|Context Sensitive
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
 +
| {{UD}}
 +
| {{UD}}
 
|-
 
|-
−
|Kleene star
+
|Recursive
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
| {{Yes}}
+
| {{UD}}
−
|-
+
| {{UD}}
−
|Homomorphism
+
| {{UD}}
−
| {{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
 +
| {{UD}}
 +
| {{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 ==
 +
[http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf Proofs]
 +
===For arbitrary CFGs <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>===
 +
The following problems are '''undecidable''':
 +
 +
# Whether <math>(L(G_1))^\complement</math> is a CFL?
 +
# Whether <math>L(G_1) \cap L(G2)</math> is a CFL? (undecidable for DCFG also)
 +
# Whether <math>L(G_1) \cap L(G2)</math> is empty? (undecidable for DCFG also)
 +
# Whether <math>L(G) = L(R)</math>?
 +
# Whether <math>L(R) \subseteq L(G)</math>?
 +
# Whether <math>G</math> is ambiguous?
 +
# Whether <math>L(G)</math> is a DCFL?
 +
# Whether <math>L(G)</math> is a regular language?
 +
 +
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 <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>===
 +
The following problems are '''decidable''':
 +
 +
# Whether <math>(L(G_1))^\complement</math> is a DCFL? (trivial)
 +
# Whether <math>L(G) = L(R)</math>?
 +
# Whether <math>L(G) \subseteq (R)</math>?
 +
# Whether <math>L(R) \subseteq L(G)</math>?
 +
# Whether <math>L(G)</math> is a CFL? (trivial)
 +
 +
 +
 +
{{Template:FBD}}
 +
 +
[[Category: Automata Theory Notes]]
 +
 +
[[Category: Compact Notes for Reference of Understanding]]

Latest revision as of 16:01, 9 January 2016

Heads Up! Please don't byheart this table. This is just to check your understanding
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 regular? $L(G)$ is finite?
Regular Grammar D D D D D D D D
Det. Context Free D D D UD D UD D D
Context Free D D UD UD UD UD UD D
Context Sensitive D UD UD UD UD UD UD UD
Recursive D UD UD UD UD UD UD UD
Recursively Enumerable UD 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

Proofs

For arbitrary CFGs <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>

The following problems are undecidable:

  1. Whether <math>(L(G_1))^\complement</math> is a CFL?
  2. Whether <math>L(G_1) \cap L(G2)</math> is a CFL? (undecidable for DCFG also)
  3. Whether <math>L(G_1) \cap L(G2)</math> is empty? (undecidable for DCFG also)
  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?
  8. Whether <math>L(G)</math> is a regular language?

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 <math>G</math>, <math>G_1</math> and <math>G_2</math> and an arbitrary regular expression <math>R</math>

The following problems are decidable:

  1. Whether <math>(L(G_1))^\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
Retrieved from "https://gatecse.in/w/index.php?title=Grammar:_Decidable_and_Undecidable_Problems&oldid=5611"
Grammar: Decidable and Undecidable Problems
Grammar <math>w \in L(M)</math> <math>L(M) = \phi</math> <math>L = \Sigma^*</math> <math>L(M_1) \subseteq L(M_2)</math> <math>L(M_1) = L(M_2)</math> <math>L(M_1) \cap L(M_2) = \phi</math>
Union Yes No Yes Yes Yes Yes
Intersection Yes No No Yes Yes Yes
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