Identify the language

Question

L₁ = {w | length of w is odd and its middle symbol is 0, w $\epsilon$ (0,1)*}

Is it regular, a CFL or a CSL?

Comments

it will be NCFL...

---

CFG for it would be??

---

the language L={ w0x | w,x ϵ(a+b)* AND |w|=|x|}.. it is clearly visible it is NCFL..keep pushing upto 'w' on stack untill 0 is encountered, than pop out one element from stack cooresponding to one character in 'x'...if finally the stack is empty..string will be accepted...and this work is to be done non deterministically since we dont know whether it is middle 0 or not..

writing Grammer is little bit difficult, but it can be conclude just by intution..

---

CFG:

S→ 0S0 | 0S1 | 1S0 | 1S1 | 0

Will be NCFL because of 0S0 and 0S1 case.

Answer 1

It must be regular. Regular expression for this,would be : [(0+1)(0+1)]*0 [(0+1)(0+1)]*

Comments

Your regular expression accepts the string 0001111 and here 0 isn't the middle symbol

---

@atul @bhavana
I am getting that it is not a RL as in FA we cannot determine the middle of a string,  but unable to write a CFG for this.

---

thnku for clearing this confusion