Arjun Suresh (talk | contribs) m (→Some Twisted Examples) |
Arjun Suresh (talk | contribs) (→Some Twisted Examples) |
||
Line 21: | Line 21: | ||
− | ===1. $L = \{ww \mid w ∈ | + | ===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 <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 ∈ | + | ===2. $L = \{ww\mid w ∈ (a+b)^+\}$=== |
Same explanation as above, <math>L</math> is <math>CSL</math>. | Same explanation as above, <math>L</math> is <math>CSL</math>. | ||
− | ===3. $L = \{ww_R\mid w ∈ | + | ===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>. | <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 | + | ===4. $L = \{ww_R\mid w ∈ \{{a+b}\}^+\}$=== |
Same explanation as above. <math>L</math> is <math>CFL</math>. | Same explanation as above. <math>L</math> is <math>CFL</math>. | ||
− | ===5. $L = \{wxw \mid w,x ∈ \{{a | + | ===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> | <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. | 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 | + | ===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>. | <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 | + | ===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> | <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 | 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 | + | ===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 | + | 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}\}^+\}$=== | ||
+ | |||
+ | L = {wxwy | x,y,w∈(a+b)+} | ||
+ | b. L = {xwyw | x,y,w∈(a+b)+} | ||
+ | c. L = {wxyw | x,y,w∈(a+b)+} | ||
{{Template:FBD}} | {{Template:FBD}} |
Find the set of strings generated by <math>L</math>
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.
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>.
Same explanation as above, <math>L</math> is <math>CSL</math>.
<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>.
Same explanation as above. <math>L</math> is <math>CFL</math>.
<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.
<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>.
<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.
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>.
L = {wxwy | x,y,w∈(a+b)+} b. L = {xwyw | x,y,w∈(a+b)+} c. L = {wxyw | x,y,w∈(a+b)+}
Find the set of strings generated by <math>L</math>
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.
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>.
Same explanation as above, <math>L</math> is <math>CSL</math>.
<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>.
Same explanation as above. <math>L</math> is <math>CFL</math>.
<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.
<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>.
<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.
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 an <math>NFA</math> making <math>L</math> regular . Regular expression for <math>L</math> is <math>a(a+b)^+a + b(a+b)^+b</math>.