(Some Twisted Examples)
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.
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})^+\}$===

Revision as of 15:48, 12 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