FOR FREE CONTENT

Important Examples: 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 4,  Example 5

Solutions:

Answer:

In our given language, 

It is clear that this language has only one infinite comparison,

From this language, we can easily say that push and pop are cleared in that case.

Still, we check how push and pop are cleared.

1. Push all ‘a’s into the stack. 

2. Push all ‘b’s into the stack. 

3. Pop all ‘b’s when every time we will get ‘c’ at the input.  Now all ‘b’s will be removed after some time but ‘c’ is still present in the input.

4. Now, the top of the stack is ‘a’s, so Pop all ‘a’s when every time we will get ‘c’ at the input.  Now all ‘a’s will be removed and stack will become empty and input will be also empty because we know: 

Now we take an example to clear the concept: 

Let the string is aabbbccccc

Here push and pop are cleared by the single stack.

Answer:

This given language 

has only one infinite comparison.  

This language is similar to the previous example, 

Example 1 just only difference with is small alteration of symbols.

Even push and pop are cleared in that case.

Still, we check how push and pop will be cleared.

1. Push all ‘a’s into the stack 

2. Pop all ‘a’s from stack whenever we will get ‘b’ at the input.  Now all ‘b’s will be unfilled at input after some operation but still, some ‘a’s are present at stack.

3. Pop all rest of ‘a’s from the stack when every time we will get ‘c’ at the input.  Now all rest of ‘a’s will be removed and the stack will become empty, even input will be also empty.

Now we take an example to clear the concept: 

Let string is aaaaa bb ccc

So, push and pop is cleared.

Answer:

In this language 

has only one infinite comparison but if we notice the condition it has a multiplication 

As we know multiplication of infinite numbers is only possible by Linear Bounded Automata or above and language is Context-Sensitive Language (CSL).

For more details follow this chapter: Non-linear power