FOR FREE YEAR SOLVED

Important Examples: Identification of language

Identify the language category:

You should know:

Before we see the solution of all given languages please follow previous chapters and examples: How to identify language,  Example 3, Language Identification: Important points.

Solutions:

Answer:

This given same language is already discussed in Example 3 

This language has two infinite comparisons ‘a’ & ‘b’ and ‘b’ & ‘c’.

So, more than one infinite comparison is always Context-Sensitive Language (CSL).

For more details visit to see Example 3.

Answer:

It is clear that given language has three infinite comparisons at a time i.e. ‘a’ & ‘b’ and ‘b’ & ‘c’ and ‘c’ &‘d’.

And we know very well that more than one infinite comparison only possible with Linear Bounded Automata and language is Context-Sensitive language.

To clear the basic concept of language identification please follow the previous chapter: How to identify language.

Answer:

And 

So, as we know any language with non-linear power is only possible by Linear Bounded Automata and language is Context-Sensitive language.

For more details see chapter: Language Identification: Important points.

Answer:

This given language has two comparisons i.e. number of ‘a’ with the number of ‘b’ and number of ‘c’ with the number of ‘d’ but this two comparison is not at a time.

First, we compare the number of ‘a’ with the number of ‘b’ after finished it then we will check the number of ‘c’ with the number of ‘d’.

In this case, it is very easy to check both comparisons because push and pop are cleared i.e. by a single use of stack we can solve this problem.

Push all ‘a’s and pop every time when ‘b’ will come so, the stack will be empty after deleting all ‘a’s by ‘b’s because of the number of ‘a’ = number of ‘b’.

Now, after completed first operation stack is empty, we will start the second one. 

Push all ‘c’s and pop every time when ‘d’ will come so, stack will be empty after deleting all ‘c’s by ‘d’s because of the number of ‘c’ = number of ‘d’.

As an example, 

We can write the string as: aaa bbb ccc ddd

Because push and pop are cleared so, this language is Deterministic Context-Free Language (DCFL).

Answer:

This language is the same as previous Example 4 

Just only difference is an alteration of power m and n.

So, it has two infinite comparisons but not at a time and push, pop is cleared.

For details concept please follow the previous example: Example 4.