FOR FREE YEAR SOLVED

Some Exercise and Solve 

Solution:

It is simple here only one comparison is present because ‘ab’ and ‘cd’ both are treated as single symbols like a and b.

So, one comparison and push, pop is cleared. 

Push all ‘ab’ on the stack and whenever we get ‘cd’ pop ‘ab’ from the stack. If the stack is empty (number of ‘ab’ equals to the number of ‘cd’ then the string is accepted.

There is no comparison is present in this language because n and m are independent. Only infinite order is present. 

We already solve this type of problem earlier. Here one comparison is present and push, pop is cleared also.

Here the power of first ‘a’ is the sum of the power of ‘b’ and next ‘a’. Push all first a’s on the stack. When we get ‘b’ pop a’s which is on the stack and the same way when we get next ‘a’ in input pop ‘a’ which is on top of the stack.

If the stack is empty i.e. number of first ‘a’ is equal to the number of ‘b’ + number second a’s, then the string is accepted.

If we see carefully it has two infinite comparisons at a time, 

And

Because there is at a time two infinite comparison we cannot solve it by stack (Stack only works with at a time one comparison which follows LIFO order). 

So, it is not Context-Free Language (CFL).

Note: Actually DCFL is less power than NCFL (DCFL < NCFL). So, we consider CFL as NCFL sometimes because it is of the highest power of CFL.

It is almost the same as the above example. 

It has two infinite comparisons at a time, 

And

As we know at a time two comparison is only done by Context-Sensitive Language (CSL).

Generally, we think in this language one comparison is present. The first number of ‘a’ with the second number of ‘a’. But it is not true same symbol not require to compare with the same symbol. 

It is almost the same above language because ‘ab’ is treated as a single symbol just like ‘a’ in the above example.

So, as we know there is no requirement to compare with the same symbol.