FOR FREE MATERIALS

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 1, Example 4

Solutions:

Answer:

This given language 

has only one infinite comparison 

i.e. number of ‘a’+ number of ‘b’= number of ‘c’ + number of ‘d’.

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. Push all ‘b’s into the stack.

3. Now, the top of the stack is ‘b’. Pop ‘b’s from stack whenever we will get ‘c’ at the input. After this operation, some cases will happen.

Cases:

A. All ‘b’s will be removed from the stack and still ‘c’ will present at the input.

B. All ‘c’s will be unfilled from input and still ‘b’ will present at stack.

C. All ‘b’s will be removed from the stack and even all ‘c’s will be unfilled from the input.

The next operation depends on the above 3 cases which one will occur.

Case A:

If case A occurs (All ‘b’s will be removed from the stack and still ‘c’ will present at input). Now the top of the stack is ‘a’ then Pop all ‘a’s from the stack whenever we will get the rest of ‘c’ at the input. 

After the operation, all ‘c’s will be unfilled from input and some of ‘a’ will still present at stack.

Exceptional Case:

Along with ‘c’ at input, all ‘a’s also removed from stack if q = 0. 

If we do not consider the exceptional case then right now top of the stack is ‘a’ and input is ‘d’. Pop all rest of ‘a’s from stack whenever we will get ‘d’ at the input. After the operation, the stack will be empty and the input will be empty. 

Then Push and Pop are cleared.

Case B:

If case B occurs (All ‘c’s will be unfilled from input and still ‘b’ will present at stack). Now at the moment ‘d’ will present at the input. So, pop all rest of ‘b’ from the stack when input is ‘d’.

After the operation, all rest of the ‘b’s will be removed from the stack, and but ‘d’ will still present at the input.

Right now top of the stack is ‘a’. So, pop all ‘a’s from stack whenever input is ‘d’.  After the operation, the stack will be empty and the input will be empty. 

Then Push and Pop are cleared.

Case C:

If case C occurs (All ‘b’s will be removed from the stack and even all ‘c’s will be unfilled from input). Right now the top of the stack is ‘a’ and input is ‘d’. So, Pop all ‘a’s from stack whenever we will get ‘d’ at the input. After the operation, the stack will be empty and the input will be empty. 

Then Push and Pop are cleared.

Now we take an example to clear the concept: 

Let string is aabbb ccddd

So, push and pop is cleared in that case.

So, this given language is Deterministic Context-Free Language (DCFL) but not Regular.

Answer: 

We already discuss this type of language in the previous examples like Example 4.

In that case given language is similar to the previous example Example 4.

We know‘∪’ (Union) and OR is the same.

So, this given language

has two infinite conditions but in between two conditions Union (‘∪’) operator is present. As we know the property of Union (‘∪’) is the same as OR i.e. if any one of the conditions is true then it is true.

However, this language has two infinite conditions but not at a time i.e. conditions are coming as one after another.

Now, because this language has two distinct conditions so, we need multiple copies of the stack because by single stack push and pop will not be cleared. 

A single machine cannot work for two distinct conditions, so, we need two multiple copies of machine work for more than one condition i.e. here it creates two copies of machine for two distinct conditions. 

Only Non-Deterministic Context-Free Language (NCFL) can work with multiple copies of the stack but Deterministic Context-Free Language (DCFL) works with a single stack.

Important Note:

Any language with multiple conditions but separated by ‘OR’  or  ‘∪’ is definitely NCFL but not DCFL. 

Exception:

Sometimes this kind of problem has some exceptions so we should do it carefully in the examination.

Identify the language:

Answer: 

This given language 

This looks similar to the above example –  

As we came to know from above last example that any language with multiple conditions but separated by ‘OR’  or Union (∪) is definitely a Non-Deterministic Context-Free Language (NCFL) because in these case multiple conditions do not occur at a time and due to distinct multiple conditions are present we need multiple copies of stack.

Actually, some language has one comparison but it looks like two comparisons because it is separated by  ‘OR’ or  Union (∪).

In our given problem,

Actually, it has one comparison because push & pop is cleared. Here ‘c’ and ‘d’ work as special symbol separators.

Sometimes to make the problem tricky, however, some language has one condition, it is represented in such a manner (one condition separated by two using Union (∪)) that it looks like a language that has two or more than two conditions.

So, this language looks like Non-Deterministic Context-Free Language (NCFL) but it is a Deterministic Context-Free Language (DCFL)

Now we check why it is DCFL:

It uses a single stack and push and pop is cleared. Because first, we push a into the stack, when we get c (separator) then pop the corresponding b’s.

Again we push a into the stack and when we get d then pop all b’s by a. After the operation stack will be empty and the input tape will also be empty.

Example: