1

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.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Bardya Momeni
  • 337
  • 4
  • 13
  • Why do you think it needs two stacks? Are you sure they cannot be combined into a single stack? – ibid Apr 08 '13 at 14:08
  • @ibid: one stack saves to number of a's by pushing a's inside it, one stack saves W, which then pops the W elements to make it reverse and then with each pop of first stack, we put b's at the end to match the number of a's. you see, you cannot merge a's and W into the same stack and know when the W or R(W) is finished. so we need two stacks. may comment? – Bardya Momeni Apr 08 '13 at 14:21
  • I see there's already an answer that makes the point I was making :-) – ibid Apr 09 '13 at 08:33

1 Answers1

1

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)

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • *let me know my answer helps or you need more details* – Grijesh Chauhan Apr 08 '13 at 17:53
  • it's a little confusing, I mean, even in an NPDA, we cant know when W is finished to stop popping and start analyzing stack content to have the b suffixes. for example, you have aaa aab baa bbb, you push aaa, then aab, now pop b - a - a - [ now we can't know to stop popping, or start putting b's - thanks – Bardya Momeni Apr 08 '13 at 20:50
  • assume we have aa bbaab baabb bb , the stack operation is put(a,a,b,b,a,a,b) then popping starts like this: if top of stack equals input then pop go to next input and repeat, else if top of stack isn't equal to input, pop stack and put b, until stack is empty... so, this can be accepted by one stack. – Bardya Momeni Apr 08 '13 at 21:49
  • @BardyaMomeni But in NPDA your have morre then one choice move from one configuration to next configuration, Hence While on one state you can push and pop both for same configuration [Learn PDA for WWr](http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/PDA.pdf) The example will clear you concept between NPDA and PDA. – Grijesh Chauhan Apr 09 '13 at 09:57
  • 1
    thank you Grijesh for your complete, through and accurate answer. – Bardya Momeni Apr 09 '13 at 12:31
  • @BardyaMomeni If you wants I can add good details in answer but you have to wait for that...you may find some other helpful on "Formal Languages and Automata Theory" through my profile... – Grijesh Chauhan Apr 09 '13 at 13:13