[SOLVED] What is this grammar? Context-free or context sensitive

What is this grammar? Context-free or context sensitive

I am studying Formal Languages and Automata Theory, and I have a question about a problem inside the book that is not answered in it. the question is:

Is this language Context Free, Regular or Context Sensitive?

L= {aⁿw w^Rbⁿ| w is ( a+b )*, w^R is reverse of w and n>=0 }

I think this language is context-sensitive, cause it needs at least two stacks for accepting.

May anybody comment on that?

thanks.

Solution

Language aⁿw w^Rbⁿ is Context Free language. We can write context free Grammar for this language.

S -->  aSb | R
R -->  aRa | bRb | ^

^ is null symbol

PDA: for language aⁿw w^Rbⁿ

push prefix string aⁿ
push w
pop w while match each symbol against symbol in w^R
pop all a pushed in stack and match against b in suffix bⁿ

Note: we while processing string of language aⁿw w^Rbⁿ through PDA we don't know where prefix aⁿ ends then where w ends before w^R starts so for this language we can't draw a deterministic model of PDA although Non-deterministic PDA is possible. And Important thing is class of non-deterministic PDA is not same as class of deterministic PDA that means scope deterministic context free languages are not equals to non-deterministic context free. (actually deterministic is subset of non-deterministic CFL)