FOR FREE MATERIALS

Example CSL: Identification of language

Identification of language:

You should know:

Before seeing the solution please follow the previous chapter to clear the concept How to identify language, Example 5, Example 3.

Solutions:

Answer:

From this given language 

It is clear that it has two infinite comparisons at a time which is m ≤ n ≤ p i.e. m ≤ n and  n ≤ p.

From chapter Identification of Language How to identify language  we know that any language which has more than one infinite comparison at a time then it can be only solved by Linear Bounded Automata and language is Context-Sensitive Language. 

Answer: 

In some previous example Example 4

and can say another language like 

In the above two cases, however, it has two infinite comparisons but not at a time and push and pop are cleared. This is the reason both are Deterministic Context-Free Language (DCFL). 

For details please see previous example Example 4 and Mock 8 TOC

Now, if we consider our given language, 

though it looks similar to the above two languages it has two comparisons at a time.

So, in the given problem language has two comparisons at a time i.e. the number of ‘a’ with the number of ‘c’ and number of ‘b’ with the number of ‘d’.

As we know any language with more than one infinite range is Context-Sensitive Language. 

Even if we try to solve it by stack then it will not work i.e. push & pop will never be cleared.

Check push and pop is possible or not?

Here we have to check, number of ‘a’ with the number of ‘c’ and the number of ‘b’ with the number of ‘d’ 

We take an example string is aabbbccddd. 

We can write this way aa bbb cc ddd.

i. Push all ‘a’s into the stack 

ii. Push all ‘b’s into the stack  (Because ‘a’ and ‘b’ has no comparison so, we cannot remove ‘a’ with ‘b’)

iii. Now when ‘c’ comes to the picture, we cannot decide what we do, because the top of the stack is ‘b’ but we cannot delete ‘b’ by ‘c’ because there is no comparison between ‘b’ and ‘c’.

Actually, there is a comparison between ‘a’ and ‘c’ but we cannot access ‘a’ because the top of the stack is ‘b’.

So, we cannot proceed further.

Answer:

If we see one previous example, 

Mock 8 TOC (click here to in details)

Now, if we see our given language 

This looks like same as the previous example above but the only difference is the range.

In this previous example, 

Language has two infinite comparisons but not at a time and push & pop is cleared  (for details please follow Mock 8 TOC ) that’s why it is DCFL.

But in our problem, 

Though this language looks like same as above it has two comparisons at a time and push & pop will not be possible. 

In that case, by stack, this problem cannot be solved because it has an extra condition i.e. m > n which makes this language a little bit complex.

So, it has two comparisons at a time then it is Context-Sensitive Language.