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

(→‎Note)
 
(43 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
Line 9: Line 11:
 
! <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)</math> is regular?
 +
! $L(G)$ is finite?
 
|-
 
|-
−
|Regular
+
|Regular Grammar
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
 +
| {{D}}
 +
| {{D}}
 
|-
 
|-
−
|DCFG
+
|Det. Context Free
−
| {{Yes}}
+
| {{D}}
−
| {{Yes}}
+
| {{D}}
−
| {{No}}
+
| {{D}}
−
| {{No}}
+
| {{UD}}
−
| {{?}}
+
| {{D}}
−
| {{No}}
+
| {{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(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