#Applied Course

Question

Please explain this.

Answer 1

The question is asking if given language is CFL or not.

In the answer it tells it is, and how.

L = $0^{m}$$1^{n}$$1^{m}$$0^{n}$

Assuming you are not friendly with the working of how CFLs are accepted:

We know CFL uses a stack(PDA) to keep track of the language: Say you want to know if $a^{k}$$b^{k}$ is CFL or not; You make a stack, have an initial symbol in stack (at top, say Z), push another symbol K for every a inputted (k times).Then on encountering b everytime, you pop a K from the top of the stack. For this language, if no of times b inputted = no of times of a, then language is accepted, so at the end all Ks put in stack by a are popped by b, we get Z back on top again and its accepted (PDA by final state)

In this case , as we cannot directly compare $0^{m}$ with $1^{n}$ on the stack, we re-arrange the terms as    $0^{m}$$1^{m}$$1^{n}$$0^{n}$.

So that stack gets m ‘M’ symbols pushed for 0, then same m no of ‘M’ symbols get popped by 1. Same is done with n no of ‘N’ symbols. And the language is accepted.