(Some Twisted Examples)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
==Given a description of a language <math>L</math>, how to find the class of <math>L</math>?==
+
==Given a description of a language $L$, how to find the class of $L$?==
  
Find the set of strings generated by <math>L</math>
+
Find the set of strings generated by $L$
# If the set of strings in <math>L</math> is finite, <math>L</math> is regular since all finite languages are regular
+
# If the set of strings in $L$ is finite, $L$ is regular since all finite languages are regular
# If the set of strings in <math>L</math> is infinite, check if we can draw an NFA for recognizing <math>L</math>. If so, <math>L</math> is regular
+
# If the set of strings in $L$ is infinite, check if we can draw an NFA for recognizing $L$. If so, $L$ is regular
# If  <math>NFA</math> is not possible for <math>L</math>, check if we can recognize <math>L</math> using a <math>PDA</math>, that is with a stack in addition to set of states. If so, <math>L</math> is <math>CFL</math>.
+
# If  $NFA$ is not possible for $L$, check if we can recognize $L$ using a $PDA$, that is with a stack in addition to set of states. If so, $L$ is $CFL$.
# If the moves of <math>PDA</math> are all deterministic, then <math>L</math> is a <math>DCFL</math>
+
# If the moves of $PDA$ are all deterministic, then $L$ is a $DCFL$
# If <math>PDA</math> is not possible for <math>L</math>, see if we can get a <math>TM</math> for <math>L</math>
+
# If $PDA$ is not possible for $L$, see if we can get a $TM$ for $L$
# If <math>TM</math> takes only a linear space (in terms of length of input string), then <math>L</math> is <math>CSL</math>. otherwise its just recursive
+
# If $TM$ takes only a linear space (in terms of length of input string), then $L$ is $CSL$. otherwise its just recursive
# If <math>L</math> is a decision problem and $TM$ can just say "yes" and may not halt in case of "no", then <math>L</math> is recursively enumerable (partially decidable).  
+
# If $L$ is a decision problem and $TM$ can just say "yes" and may not halt in case of "no", then $L$ is recursively enumerable (partially decidable).  
#If <math>TM</math> can say both "yes" and "no" then <math>L</math> is recursive
+
#If $TM$ can say both "yes" and "no" then $L$ is recursive
# If no <math>TM</math> is possible for <math>L</math>, then <math>L</math> is undecidable
+
# If no $TM$ is possible for $L$, then $L$ is undecidable
  
 
==Some Facts==
 
==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.
<math>P</math>, <math>NP</math> and <math>NPC</math> problems can all be decided by a <math>TM</math> 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==
 
==Some Twisted Examples==
Line 22: Line 22:
  
 
===1.  $L = \{ww \mid w ∈ (a+b)^*\}$===
 
===1.  $L = \{ww \mid w ∈ (a+b)^*\}$===
The set of strings in <math>L</math> are <math>\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}</math>. We cannot accept these strings using an <math>NFA</math>. Now, even a <math>PDA</math> is not possible as once we store <math>w</math> on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize <math>L</math>. Now, <math>L</math> can be accepted by a <math>TM</math> in linear space and hence <math>L</math> is <math>CSL</math>.  
+
The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$.  
  
 
===2.  $L = \{ww\mid w ∈ (a+b)^+\}$===
 
===2.  $L = \{ww\mid w ∈ (a+b)^+\}$===
Same explanation as above, <math>L</math> is <math>CSL</math>.
+
Same explanation as above, $L$ is $CSL$.
  
 
===3.  $L = \{ww_R\mid w ∈ ({a+b})^*\}$===
 
===3.  $L = \{ww_R\mid w ∈ ({a+b})^*\}$===
<math>ww_R</math> can be accepted by a <math>PDA</math> and hence is <math>CFL</math>. But we need a <math>NPDA</math> for this as there is no deterministic way to identify where <math>w</math> ends and <math>w_R</math> starts. <math>wcw_R, w\in(a+b)^*</math> is accepted by a <math>DPDA</math> and hence is <math>DCFL</math>.
+
$ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$.
  
 
===4.  $L = \{ww_R\mid w ∈ ({a+b})^+\}$===
 
===4.  $L = \{ww_R\mid w ∈ ({a+b})^+\}$===
Same explanation as above. <math>L</math> is <math>CFL</math>.
+
Same explanation as above. $L$ is $CFL$.
  
 
===5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $===
 
===5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $===
<math>L</math> is regular since <math> L =  \Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</math>.  i.e.; the set of strings generated by <math>L</math> is <math>\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*</math>
+
$L$ is regular since $ L =  \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$.  i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
  
 
This language is different from the  $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.
 
This language is different from the  $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.
  
 
===6.  $L = \{wxw\mid w,x ∈ ({a+b})^+\}$===
 
===6.  $L = \{wxw\mid w,x ∈ ({a+b})^+\}$===
<math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not contained in <math>L</math>. All words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings  we need  a <math>TM</math> with linear space (this is at least as hard as accepting <math>ww, w \in (a+b)^*</math>), making <math>L</math>, a <math>CSL</math>.
+
$L$ doesn't contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings  we need  a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$.
  
 
===7.  $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$===
 
===7.  $L = \{wxw_R\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>
+
$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*, making L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
  
 
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.
 
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})^+\}$===
 
===8.  $L = \{wxw_R\mid w,x ∈ ({a+b})^+\}$===
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>.
+
The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, ...\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn't contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+b$.
  
 
===9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$===
 
===9. $L = \{wxwy \mid w,x,y ∈ ({a+b})^+\}$===
Line 61: Line 61:
  
 
===12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$===
 
===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>
+
$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$
  
 
===13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$===
 
===13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$===

Latest revision as of 16:35, 17 November 2015

Given a description of a language $L$, how to find the class of $L$?

Find the set of strings generated by $L$

  1. If the set of strings in $L$ is finite, $L$ is regular since all finite languages are regular
  2. If the set of strings in $L$ is infinite, check if we can draw an NFA for recognizing $L$. If so, $L$ is regular
  3. If $NFA$ is not possible for $L$, check if we can recognize $L$ using a $PDA$, that is with a stack in addition to set of states. If so, $L$ is $CFL$.
  4. If the moves of $PDA$ are all deterministic, then $L$ is a $DCFL$
  5. If $PDA$ is not possible for $L$, see if we can get a $TM$ for $L$
  6. If $TM$ takes only a linear space (in terms of length of input string), then $L$ is $CSL$. otherwise its just recursive
  7. If $L$ is a decision problem and $TM$ can just say "yes" and may not halt in case of "no", then $L$ is recursively enumerable (partially decidable).
  8. If $TM$ can say both "yes" and "no" then $L$ is recursive
  9. If no $TM$ is possible for $L$, then $L$ is undecidable

Some Facts

  • 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.
  • 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.

Some Twisted Examples

1. $L = \{ww \mid w ∈ (a+b)^*\}$

The set of strings in $L$ are $\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}$. We cannot accept these strings using an $NFA$. Now, even a $PDA$ is not possible as once we store $w$ on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize $L$. Now, $L$ can be accepted by a $TM$ in linear space and hence $L$ is $CSL$.

2. $L = \{ww\mid w ∈ (a+b)^+\}$

Same explanation as above, $L$ is $CSL$.

3. $L = \{ww_R\mid w ∈ ({a+b})^*\}$

$ww_R$ can be accepted by a $PDA$ and hence is $CFL$. But we need a $NPDA$ for this as there is no deterministic way to identify where $w$ ends and $w_R$ starts. $wcw_R, w\in(a+b)^*$ is accepted by a $DPDA$ and hence is $DCFL$.

4. $L = \{ww_R\mid w ∈ ({a+b})^+\}$

Same explanation as above. $L$ is $CFL$.

5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $

$L$ is regular since $ L = \Sigma^*$, by making $x = (a+b)^*$ and $w = \epsilon$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$

This language is different from the $L = \{wcw \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.

6. $L = \{wxw\mid w,x ∈ ({a+b})^+\}$

$L$ doesn't contain all strings in $\Sigma^*$ as the strings like $abab$ are not contained in $L$. All words starting and ending in $a$ or starting and ending in $b$ are in $L$. But $L$ also contains words starting with $a$ and ending in $b$ like $abbab, aabbbabaab$ etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a $TM$ with linear space (this is at least as hard as accepting $ww, w \in (a+b)^*$), making $L$, a $CSL$.

7. $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*, making L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$

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})^+\}$

The set of strings in $L$ are $\{aaa, aba, aaaa, aaba, abaa, abba, baab, ...\}$ i.e.; $L$ contains all strings starting and ending with $a$ or starting and ending with $b$ and containing at least 3 letters. Moreover, $L$ doesn't contain any other strings. Thus $L$ can be accepted by a finite automata making $L$ regular . Regular expression for $L$ is $a(a+b)^+a + b(a+b)^+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})^+\}$

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})^+\}$

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.

12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$

$L$ is regular. Since, $w$ can be $\epsilon$ and $x \in (a+b)^*$, making $L =\Sigma^*$. i.e.; the set of strings generated by $L$ is $\{ \epsilon, a, b, aa, ab, ba, bb, aaa, ...\} = \Sigma^*$

13. $L = \{xww \mid w,x ∈ ({a+b})^+\}$

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL.

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 (non-determinism is required to guess the start of $w$).




blog comments powered by Disqus

Given a description of a language <math>L</math>, how to find the class of <math>L</math>?[edit]

Find the set of strings generated by <math>L</math>

  1. If the set of strings in <math>L</math> is finite, <math>L</math> is regular since all finite languages are regular
  2. If the set of strings in <math>L</math> is infinite, check if we can draw an NFA for recognizing <math>L</math>. If so, <math>L</math> is regular
  3. If <math>NFA</math> is not possible for <math>L</math>, check if we can recognize <math>L</math> using a <math>PDA</math>, that is with a stack in addition to set of states. If so, <math>L</math> is <math>CFL</math>.
  4. If the moves of <math>PDA</math> are all deterministic, then <math>L</math> is a <math>DCFL</math>
  5. If <math>PDA</math> is not possible for <math>L</math>, see if we can get a <math>TM</math> for <math>L</math>
  6. If <math>TM</math> takes only a linear space (in terms of length of input string), then <math>L</math> is <math>CSL</math>. otherwise its just recursive
  7. If <math>L</math> is a decision problem and $TM$ can just say "yes" and may not halt in case of "no", then <math>L</math> is recursively enumerable (partially decidable).
  8. If <math>TM</math> can say both "yes" and "no" then <math>L</math> is recursive
  9. If no <math>TM</math> is possible for <math>L</math>, then <math>L</math> is undecidable

Some Facts[edit]

Partially undecidable or semi-undecidable is considered undecidable. For example halting problem is considered  undecidable but is semi-decidable.
<math>P</math>, <math>NP</math> and <math>NPC</math> problems can all be decided by a <math>TM</math> and hence are recursive. 
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.

Some Twisted Examples[edit]

1. $L = \{ww \mid w ∈ (a+b)^*\}$[edit]

The set of strings in <math>L</math> are <math>\{aa, bb, aaaa, abab, baba, bbbb, aaaaaa, ...\}</math>. We cannot accept these strings using an <math>NFA</math>. Now, even a <math>PDA</math> is not possible as once we store <math>w</math> on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize <math>L</math>. Now, <math>L</math> can be accepted by a <math>TM</math> in linear space and hence <math>L</math> is <math>CSL</math>.

2. $L = \{ww\mid w ∈ (a+b)^+\}$[edit]

Same explanation as above, <math>L</math> is <math>CSL</math>.

3. $L = \{ww_R\mid w ∈ ({a+b})^*\}$[edit]

<math>ww_R</math> can be accepted by a <math>PDA</math> and hence is <math>CFL</math>. But we need a <math>NPDA</math> for this as there is no deterministic way to identify where <math>w</math> ends and <math>w_R</math> starts. <math>wcw_R, w\in(a+b)^*</math> is accepted by a <math>DPDA</math> and hence is <math>DCFL</math>.

4. $L = \{ww_R\mid w ∈ ({a+b})^+\}$[edit]

Same explanation as above. <math>L</math> is <math>CFL</math>.

5. $L = \{wxw \mid w,x ∈ ({a+b})^*\} $[edit]

<math>L</math> is regular since <math> L = \Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</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 \mid w ∈ ({a,b})^*\} $ which is clearly a CSL. Here, we cannot do any reduction and hence there is no way to accept a string without checking w before c and w after c are the same which requires an LBA.

6. $L = \{wxw\mid w,x ∈ ({a+b})^+\}$[edit]

<math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not contained in <math>L</math>. All words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter separates them. To accept such strings we need a <math>TM</math> with linear space (this is at least as hard as accepting <math>ww, w \in (a+b)^*</math>), making <math>L</math>, a <math>CSL</math>.

7. $L = \{wxw_R\mid w,x ∈ ({a+b})^*\}$[edit]

<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 \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})^+\}$[edit]

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})^+\}$[edit]

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})^+\}$[edit]

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})^+\}$[edit]

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.

12. $L = \{xww \mid w,x ∈ ({a+b})^*\}$[edit]

<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})^+\}$[edit]

Here, $w$ cannot be $\epsilon$ and hence to accept the string we do need the power of an LBA making $L$ a CSL.

14. $L = \{xww_R \mid w,x ∈ ({a+b})^+\}$[edit]

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$).




blog comments powered by Disqus