Consider the following languages:

$L_{1} = {w w ∣ w ϵ {a, b}^{}}$

$L_{2} = {w w^{R} ∣ w ϵ {a, b}^{}, w^{R} i s t h e r e v e r s e o f w}$

$L_{3} = {0^{2 i} ∣ i i s a n i n t e g e r}$

$L_{4} = {0^{i 2} ∣ i i s a n i n t e g e r}$

Which of the languages are regular?

Open in App

Solution

$L_{1} = {w w ∣ w ϵ {a, b}^{}}$

is context sensitive language (CSL) (since there is infinite string matching in straight order).

$L_{2} = {w w^{R} ∣ w ϵ (a, b)^{}, w^{R} i s t h e r e v e r s e o f w}$

is context free language (since there is infinite string matching in reverse order).

$L_{3} = {0^{2 i} ∣ i i s a n i n t e g e r} = (00)^{*}$

is regular language which contains all strings having even number of 0's

$L_{4} = {0^{i 2} ∣ i i s a n i n t e g e r}$

is context sensitive language (CSL) (since the power is infinite and non linear).

Suggest Corrections

Similar questions

Consider the language L_{1} and L_{2};

L_{1} = {w w | w ϵ (a, b)^{*}}

L_{2} = {¯ L}_{1}

L_{1} : {w w | w ϵ {a}^{*}}

L_{2} : {w w | w ϵ {a b}^{*}}

L_{1}

w w^{R}

w \in

{(0, 1)}^{*}

L_{2}

w \neq w^{R}

w \in

{(0, 1)}^{*}

\neq

L_{3}

w w

w \in

{(0, 1)}^{*}

L_{1} and L 2

L_{1}

L_{2}

D C F L .

L_{3} = (L_{1} \cap L_{2}^{*})^{'}

L_{3}

L_{1} \cup L_{2}

L_{1} a n d L_{2}

Join BYJU'S Learning Program