Which of these languages are regular, CFL and CSL?

Question

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}$?

• A. All languages $L_1, L_2, L_3, L_4$ are context free languages
• B. Languages $L_1, L_3$ are context free language and $L_2, L_4$ are regular
• C. $L_1$ is context free, $L_2$ and $L_3$ are regular and $L_4$ is context sensitive languages
• D. $L_1, L_4$ are context free, $L_2$ and $L_3$ is context sensitive languages

Comments

Source of question?

---

ohhh sorry didnt check this comment here...directly looked at the comments on answer. The qestion is from gateforum online test series.

---

In L3 z€(a). What it means

Answer 1

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 WxW^R,then we could make it with stack but here it is WxW.. so not CFL but CSL

so C is the correct answer here

Comments

ok now I understand this cannot be a CFL. However still the question remains how can we be sure that the power of LBA is enough to accept this language and we will not need the power of full unrestricted Turing machine? Is there anyeasy/intuitive/quick way to imagine LBA implementing this lagnuage?

(Sir I commented about the question source above. Sorry didnt checked your comment on question, I directly checked comments here on answer. Its from gateforum online test series.)

---

okay. np. There is something I dont like about the question though it is far far better than ACE questions. For your specific question, if you can write a C code for a problem that means its language is CSL. This is technically wrong but what I meant is for all the problems which we normally do, the space complexity is always linear and hence it is CSL. We normally do not see a recursive language which is not CSL - though that exist and can be found in google.

---

How 4) is not CFL?

Answer 2

A nswer is C

is it?