FOR FREE MATERIALS

Some Exercise and Solve of Language Identification

Exercise:

Solution:

In this given language one infinite comparison is there and push, pop is cleared because the power of b is the sum of power a and c. 

Example: Here we take two examples to see how push and pop will be cleared.

So, there is one comparison and push, pop is cleared.

In this language two comparisons at a time,

As we know PDA cannot work with two infinite comparisons at a time. PDA only works with one comparison at a time. 

Context-Sensitive Language (CSL) can only able to work with two infinite comparisons at a time. 

For example 

If we look carefully at all strings which are accepted by this given language

In this language there is no comparison between n and m, only ordering is present. 

We already solve this type of problem in the previous example. Here one comparison is present and push, pop is cleared also.

Here the power of c is the sum of the power of a and b. Push all a’s on the stack and then push all b’s on the stack. When we get c pop all a’s and b’s from the stack and at last stack become empty and input c is also empty.

It is almost the same as the above language, in this language one comparison is there, and push, pop is cleared.