What is this grammar? Context-free or context sensitive

StackOverflow https://stackoverflow.com/questions/15880974

Pregunta

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= {anw wRbn| w is ( a+b )*, wR 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.

¿Fue útil?

Solución

Language anw wRbn 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 anw wRbn

  • 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 anw wRbn 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)

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top