110 views

1 Answer

0 votes
0 votes
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.

Related questions

0 votes
0 votes
0 answers
1
Dknights asked Jan 4
104 views
what should be correct according to gate PYQs?
0 votes
0 votes
1 answer
2
Dknights asked Dec 29, 2023
130 views
How I2-I4 is counted?
1 votes
1 votes
1 answer
4
Dknights asked Dec 24, 2023
143 views
I think 3rd option is right but they mentionedThe binary representation of -39 is : 10110012's complement of 1011001 will be: 1's complement of 1011001 + 1= 0100110 + 1 ...