Grammar: Decidable and Undecidable Problems - Revision history

Arjun Suresh: /* Note */

2016-01-09T16:01:22Z

‎Note

2014-11-14T14:41:51Z

2014-11-14T14:40:46Z

2014-11-14T14:38:47Z

2014-07-14T09:45:39Z

2014-07-03T19:16:14Z

2014-07-03T19:15:57Z

2014-07-03T19:15:22Z

2014-07-03T19:14:21Z

2014-07-03T19:13:32Z

@@ Line 101: / Line 101: @@
 # Whether <math>L(R) \subseteq L(G)</math>?
 # Whether <math>L(G)</math> is a CFL? (trivial)
-===Note===

@@ Line 11: / Line 11: @@
 ! <math>L(G_1) = L(G_2)</math>
 ! <math>L(G_1) \cap L(G_2) = \phi</math>
-! <math>L(G)</math> is finite?
+! <math>L(G)</math> is regular?
-! $L(G)$ is regular?
+! $L(G)$ is finite?
 |-
 |Regular Grammar
@@ Line 37: / Line 37: @@
 | {{D}}
 | {{D}}
 | {{UD}}
 | {{UD}}
@@ Line 42: / Line 43: @@
 | {{UD}}
 | {{D}}
 |-
 |Context Sensitive

@@ Line 11: / Line 11: @@
 ! <math>L(G_1) = L(G_2)</math>
 ! <math>L(G_1) \cap L(G_2) = \phi</math>
-! <math>L(G)</math> is finite
+! <math>L(G)</math> is finite?
 |-
 |Regular Grammar
 | {{D}}
 | {{D}}
@@ Line 29: / Line 31: @@
 | {{D}}
 | {{UD}}
 | {{D}}
 |-
@@ Line 39: / Line 42: @@
 | {{UD}}
 | {{D}}
 |-
 |Context Sensitive
 | {{D}}
 | {{UD}}
 | {{UD}}
@@ Line 51: / Line 56: @@
 |Recursive
 | {{D}}
 | {{UD}}
 | {{UD}}
@@ Line 59: / Line 65: @@
 |-
 |Recursively Enumerable
 | {{UD}}
 | {{UD}}

@@ Line 27: / Line 27: @@
 | {{D}}
 | {{UD}}
-| {{?}}
+| {{D}}
 | {{UD}}
 | {{D}}

@@ Line 100: / Line 100: @@
 {{Template:FBD}}
-[[Category: Automata Theory]]
+[[Category: Automata Theory Notes]]
 [[Category: Compact Notes for Reference of Understanding]]

@@ Line 95: / Line 95: @@
 # Whether <math>L(G)</math> is a CFL? (trivial)
 ===Note===
- For any $TM$ $M$, $\Sigma^*-L(M)$, is a $CFL$
+For any $TM$ $M$, $\Sigma^*-L(M)$, is a $CFL$

← Older revision		Revision as of 19:15, 3 July 2014
Line 95:		Line 95:
	# Whether <math>L(G)</math> is a CFL? (trivial)		# Whether <math>L(G)</math> is a CFL? (trivial)

−	For any $TM$ $M$, $\~~sigma~~^*-L(M)$ is a $CFL$	+	For any $TM$ $M$, $\Sigma^*-L(M)$ is a $CFL$

@@ Line 71: / Line 71: @@
 ==Other Undecidable Problems ==
- [http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf Proofs]
+[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''':
@@ Line 95: / Line 95: @@
 # Whether <math>L(G)</math> is a CFL? (trivial)
-For any $TM$ $M$, $\Zigma^*-L(M)$ is a $CFL$
+For any $TM$ $M$, $\sigma^*-L(M)$ is a $CFL$