1,171 views
3 votes
3 votes

L={w| length of w is odd and its middle symbol is 0, wε{0,1}* }

Reg or CFL?

2 Answers

Best answer
3 votes
3 votes

The given language is an NCFL..Let us see how :

Given L = { w | middle letter is zero and length of w is odd and w belongs to (0+1)* }

So '0' will be on middle only if we have same length substring on either part of '0' ..Hence length matching now comes into play..

So we continue to push the symbols into the stack until we get the middle letter which is '0'.But '0' is the part of alphabet so we dont know with surety when will the middle letter appear so that after that we can pop the letters from the stack and reading the second substring..

Had the middle letter been not a part of alphabet then we could have done the above thing deterministically..Hence the given language is an NCFL and hence CFL but not DCFL..

selected by
0 votes
0 votes
it is saying length of the string is odd it means 3,5,,7,9 and so on... so it will be impossible in finite automata to find the middle  but we can do this with non deterministic PDA by guessing at each symbol that this will be the middle hence

NOT REGULAR NOT DCFL

BUT

CFL

 

correct me if i am wrong.

Related questions

3 votes
3 votes
0 answers
2
2 votes
2 votes
0 answers
3
Akriti sood asked Dec 18, 2016
147 views
Which of the following is true? L is Regular L is Context Free L is not Regular L is not Context Freeplease tell whether it is CFL os not?if it is,then wht will be th...
2 votes
2 votes
2 answers
4
resilientknight asked Aug 2, 2016
361 views
{0p0q+ 1p1q | 0<=p<=q } Regular or Cfl?My confusion is there is comparison involved between p and q ?