## 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 languageExamplesExamples.

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 ‘2awhen 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 languageExample 1Examples.

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 languageExample 4Example 2.

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 languageExamplesExamples.

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 languageExample 3Example 4Example 1Example 2Example 5

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.