Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
=1. $L = \{ww| w ∈ \{{a,b}\}^*\}$= | =1. $L = \{ww| w ∈ \{{a,b}\}^*\}$= | ||
| − | <math>L</math> is <math>CSL</math> as with a <math>PDA</math> we cannot accept <math>ww</math>. <math>PDA</math> is using only a stack and hence it can accept <math>ww_R</math> but not <math>ww</math>. | + | ==<math>L</math> is <math>CSL</math> as with a <math>PDA</math> we cannot accept <math>ww</math>. <math>PDA</math> is using only a stack and hence it can accept <math>ww_R</math> but not <math>ww</math>. == |
=2. $L = \{ww| w ∈ \{{a,b}\}^+\}$= | =2. $L = \{ww| w ∈ \{{a,b}\}^+\}$= | ||
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> and <math>c\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>.
<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 an <math>LBA</math> (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)^*, L =\Sigma^*</math>.
<math>L</math> is regular. <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 <math>DFA</math>. Regular expression for <math>L</math> is <math>a(a+b)^+a + b(a+b)^+b</math>.
<math>L</math> is <math>CSL</math> as with a <math>PDA</math> we cannot accept <math>ww</math>. <math>PDA</math> is using only a stack and hence it can accept <math>ww_R</math> but not <math>ww</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> and <math>c\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>.
<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 an <math>LBA</math> (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)^*, L =\Sigma^*</math>.
<math>L</math> is regular. <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 <math>DFA</math>. Regular expression for <math>L</math> is <math>a(a+b)^+a + b(a+b)^+b</math>.
GATECSE