Identify the class of the language - Revision history

Arjun Suresh at 16:35, 17 November 2015

2015-11-17T16:35:33Z

Arjun Suresh at 15:48, 12 November 2015

2015-11-12T15:48:58Z

Show changes

Arjun Suresh: /* Some Twisted Examples */

2015-11-09T10:56:17Z

‎Some Twisted Examples

Arjun Suresh: /* Some Twisted Examples */

2015-11-09T10:54:51Z

‎Some Twisted Examples

Arjun Suresh at 15:38, 12 August 2015

2015-08-12T15:38:19Z

Arjun Suresh: /* Some Twisted Examples */

2014-11-13T11:25:50Z

‎Some Twisted Examples

Arjun Suresh: /* Some Twisted Examples */

2014-11-13T11:24:31Z

‎Some Twisted Examples

Arjun Suresh: /* Some Twisted Examples */

2014-11-13T11:19:27Z

‎Some Twisted Examples

Arjun Suresh: /* Some Twisted Examples */

2014-11-13T11:18:45Z

‎Some Twisted Examples

Arjun Suresh: /* Some Twisted Examples */

2014-11-13T11:15:50Z

‎Some Twisted Examples

@@ Line 13: / Line 13: @@
 ==Some Facts==
- Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered  undecidable but is semi-decidable.
+*Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered  undecidable but is semi-decidable.
- $P$, $NP$ and $NPC$ problems can all be decided by a $TM$ and hence are recursive.
+*$P$, $NP$ and $NPC$ problems can all be decided by a $TM$ and hence are recursive.
- All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.
+*All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.
- Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable.
+*Turing decidable problems are recursive but Turing recognizable (Turing acceptable) problems are only recursively enumerable.
 ==Some Twisted Examples==

@@ Line 61: / Line 61: @@
 ===12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$===
-<math>L</math> is regular. Since, <math>w</math> can be <math>\epsilon</math> and <math>x \in (a+b)^*, making L =\Sigma^*</math>. i.e.; the set of strings generated by <math>L</math> is <math>\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*</math>
+<math>L</math> is regular. Since, <math>w</math> can be <math>\epsilon</math> and <math>x \in (a+b)^*$, making $L =\Sigma^*</math>. i.e.; the set of strings generated by <math>L</math> is <math>\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*</math>
 ===13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$===

@@ Line 44: / Line 44: @@
 <math>L</math> is regular. Since, <math>w</math> can be <math>\epsilon</math> and <math>x \in (a+b)^*, making L =\Sigma^*</math>. i.e.; the set of strings generated by <math>L</math> is <math>\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*</math>
-This language is different from the  $L = \{wcw_R | w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA.
+This language is different from the  $L = \{wcw_R \mid w ∈ \{{a,b}\}^*\} $ which is clearly a DCFL. Here, we cannot do any reduction and hence there is no way to accept a string without checking that the string after c is the reverse of the string before c, which requires a DPDA.
 ===8.  $L = \{wxw_R\mid w,x ∈ ({a+b})^+\}$===
@@ Line 67: / Line 67: @@
 ===14. $L = \{xww_R \mid w,x ∈ ({a+b})^+\}$===
-Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL.
+Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of a PDA making $L$ a NCFL (non-determinism is required to guess the start of $w$).
 {{Template:FBD}}

@@ Line 59: / Line 59: @@
 ===11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$===
 Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.
 {{Template:FBD}}

@@ Line 58: / Line 58: @@
 ===11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$===
-Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab, x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.
+Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab$ and $x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.
 {{Template:FBD}}

@@ Line 49: / Line 49: @@
 The set of strings in <math>L</math> are <math>\{aaa, aba, aaaa, aaba, abaa, abba, baab, ...\}</math> i.e.; <math>L</math> contains all strings starting and ending with <math>a</math> or starting and ending with <math>b</math> and containing at least 3 letters. Moreover, <math>L</math> doesn't contain any other strings. Thus <math>L</math> can be accepted by a finite automata making <math>L</math> regular . Regular expression for <math>L</math> is <math>a(a+b)^+a + b(a+b)^+b</math>.
-===9. $L = \{wxwy \mid w,x,y ∈ ({a,b})^+\}$===
+===9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$===
 For any string to be in $L$, the beginning part of the string ($w$) must repeat at some other point (between the second and last characters) of the string (next $w$). Since $y$ is there at the end which can generate any string, we can make $w$ as small as possible as per the given condition. So, $w$ can be either $a$ or $b$. We can thus write regular expression for $L$ as $a(a+b)^+a(a+b)^+ + b(a+b)^+b(a+b)^+$
-===10. $L = \{xwyw \mid w,x,y ∈ ({a,b})^+\}$===
+===10. $L = \{xwyw \mid w,x,y ∈ ({a+b})^+\}$===
 Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be
 $(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+b$
-===11. $L = \{wxyw \mid w,x,y ∈ ({a,b})^+\}$===
+===11. $L = \{wxyw \mid w,x,y ∈ ({a+b})^+\}$===
+Here, $w$ is coming at the beginning and also at the end. Unlike as in example 8 or 9, we cannot restrict $w$ to be $a$ or $b$ as a string starting with $a$ can end in $b$ and still be in $L$- example $abaaab$, where $w = ab, x,y = a$. In short we need to compare the substring at the beginning of the string with that at the end, making this a CSL.
 {{Template:FBD}}

← Older revision		Revision as of 11:18, 13 November 2014
Line 53:		Line 53:

	===10. $L = \{xwyw \mid w,x,y ∈ ({a,b})^+\}$===		===10. $L = \{xwyw \mid w,x,y ∈ ({a,b})^+\}$===
		+	Similar explanation for example 9, except that instead of first character being $a$ or $b$ we have the last character. So, regular expression for $L$ will be
		+	$(a+b)^+a(a+b)^+a + (a+b)^+b(a+b)^+(a+b)^+b$
		+

	===11. $L = \{wxyw \mid w,x,y ∈ ({a,b})^+\}$===		===11. $L = \{wxyw \mid w,x,y ∈ ({a,b})^+\}$===