edited by
289 views
0 votes
0 votes
L={W # W | W is in (0+1)* and # is a special symbol}

a) L is context free

b)L is accepted by turing machine for sure

c) L is non cfl

?
edited by

1 Answer

1 votes
1 votes
This is infact the terminology for the checking whether variable has been declared before use.

For this programming language construct, we need power of Context Sensitive Languages.

And surely Turing machines can accept all CSL.