CREATE OWN LIBRARY

Important Examples: Identification of language

Identification of language:

Solutions:

You should know:

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

Answer: 

In this language 

has one infinite condition i.e. number of b = twice the number of a.

Now we will check push and pop will be cleared or not.

1. Push ‘a’ twice into the stack when we will get single ‘a’ at input tape because the number of b is twice the number a. To equalize the number of b and number of a at stack to make the operation easy we push ‘2a’when we will ‘a’ at the input.

2. Pop ‘a’ from the top of the stack whenever we will get ‘b’ at input tape. After completion of operation stack and input tape will be empty. 

Example:

Let take a string aabbbb 

Now push and pop is cleared.

So, this given language has one infinite comparison and push, pop is cleared, then it is Deterministic Context-Free Language (DCFL).

You should know:

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

Answer: 

This given language 

But this comparison is finite because the range of k and n is finite i.e. n, k ≤ 0.

As you know that any language which has one or more comparison with finite range, is Regular Language.

All finite languages are Regular Language.

You should know:

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

Answer:

This given language 

has more than one infinite comparison but not at a time, because 

So, it creates multiple copies of the stack for all comparisons. 

Now, this given language has more than one comparison but not at a time and it needs multiple copies of the stack. 

So, it is a Non-Deterministic Context-Free Language (NCFL)

You should know:

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

Answer:

This language is similar to the above example Example 1

This given language 

also has one infinite condition n ≤ 5k i.e. number of a ≤ 5 times number of b. 

So, that it has one infinite condition, and if we see properly push, pop is also cleared.

This language is Deterministic Context-Free Language but not Regular.

You should know:

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

Answer:

We already discuss this type of language in the previous example like Example 1

In that case given language is similar to the previous example

We know ‘∩’ (Intersection) and AND are the same.

So, this given language

has two infinite conditions but in between two conditions Intersection (‘∩’) operator is present. As we know the property of Intersection (‘∩’) is the same as AND i.e. if both conditions are true then the total condition will true.

So, this given language has two infinite conditions at a time because of (‘∩’).

Any language with multiple conditions and if it is separated by ‘∩’ (Intersection) or AND then this language is Context Sensitive Language (CSL).

But in that case, we can think about this problem another way that if we notice the given language 

Now we know from previous example Example 3 and Example 1

because it has two infinite comparisons at a time.