FOR FREE YEAR SOLVED

Example 3          

 Solution:

Here at a time, two comparisons occurred as we know we can’t solve two comparisons at a time by the stack that’s why DCFL and NCFL only solve one comparison at a time. So, in that case, we will use tape.

So, by DCFL and NFCL we cannot solve it. We use tape here so, it will be solved by Context-Sensitive Language (CSL).

But still, we try to see why it is not possible to solve by the stack.

Let try to solve it by stack, check it is possible or not.

Example:  

The machine pushes all a’s and after it gets ‘b’ pops all ‘a’ from the stack and then the stack is empty. 

Now, ‘c c c’ is left but the stack is empty. There is no situation for comparison for ‘c c c’.

Now it is solved by tape. The tape does not follow any order.

(We can compare a  b c at a time)

Here it compares first a b c and then second a b c and so on.

So, it is CSL but not NCFL.

Take another example where the string will be rejected.

Example:

So, it is not accepted, it is rejected.

Let think it a different way and see is it possible to solve by stack or not.

Example: 

Now two (c c) left but the stack is empty. 

But some of the solvers think that they can solve it by stack by pushing ‘a’ two times on the stack when they get one ‘a’.

Like

aa     bb    cc

For single ‘a’, we push ‘a’ two times, now first ‘aa’ pop by two b’s (b b) and next two a’s (a a) pop by two c’s (c c), and now stack is empty and string is accepted.

But this process is not right. 

 i.e.

But we have to compare (a with b and b with c).

In the above problem, we solved it by false method but it is wrong. It creates some problem like -  

Put a twice after getting single a, now pop a by single b, now pop rest of three a (a a a) by three c (c c c) and now stack empty and string is accepted. But it should be rejected.

This is the problem of this method. 

The above method happened string accepted because