What is this grammar? Context-free or context sensitive

Question

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.

Answer 1

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 an
• push w
• pop w while match each symbol against symbol in wR
• pop all a pushed in stack and match against b in suffix bn

Note: we while processing string of language aⁿw w^Rbⁿ through PDA we don't know where prefix an ends then where w ends before wR 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)