edited by
2,869 views
10 votes
10 votes

Consider the following statements:

$L_1=\left\{\text{wxw$^R$|w$\in$(a,b)$^*$, x$\in$c }\right\}$

$L_2=\left\{\text{wy|w, y $\in$ (a,b)$^*$}\right\} $

$L_3=\left\{\text{zwz|w$\in$(a,b)$^*$,Z$\in$}\left\{a\right\} \right\}$

$L_4=\left\{\text{wxw|w $\in$ (a,b)$^*$, x$\in$} \left\{c\right\}^* \right\}$

Which of the following statements are $\text{CORRECT}$?

  1. All languages $L_1, L_2, L_3, L_4$ are context free languages
  2. Languages $L_1, L_3$ are context free language and $L_2, L_4$ are regular
  3. $L_1$ is context free, $L_2$ and $L_3$ are regular and $L_4$ is context sensitive languages
  4. $L_1, L_4$ are context free, $L_2$ and $L_3$ is context sensitive languages
edited by

2 Answers

2 votes
2 votes

L1= this can be easily achived by PDA ,more specifically by a DPDA .so it is a CFL

L2=it is regular language ,w.y can be anything in (a,b)* here

L3=it is nothing but the set of all languages that starts and ends with a ..so Regular

L4=it is CSL , if it was given like WxWR,then we could make it with stack but here it is WxW.. so not CFL but CSL

so C is the correct answer here

edited by

Related questions

2 votes
2 votes
1 answer
1
Tuhin Dutta asked Dec 4, 2017
682 views
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ or\ j\ \neq k\ \}$$b) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ and\ j\ \neq k\ \}$a) CFL(union of two OR-ed compa...
2 votes
2 votes
0 answers
2
2 votes
2 votes
1 answer
3