FOR FREE CONTENT

Special Cases of CSL: Example

Q. Identify the language:

a) Regular Language 

b) DCFL but not Regular

c) NCFL but not DCFL

d) CSL 

You should know:

Before seeing the solution at least we should follow How to identify language, Example 2,  Example 1, Example 3.

Solution:

Answer d is correct, this given language is Context Sensitive Language (CSL).

Explanation:

If we see the previous example Example 2 where language, 

i.e. infinite palindrome and we checked it is required multiple stacks to clear push and pop.

For details please see: Example 2.

In our given question language, 

Now, we have to check push and pop of the stack is clear for this given language or not.

And 

Example: 

In that case, we know, 

And 

if push and pop are cleared then we can say it will DCFL or NCFL depends on the use of a single or multiple time stack.

Here it is really difficult to understand up to which point of the string we will push in the stack and from where we will pop.

If we take an example ω = aab so, ωω = abbabb (concatenated string)

We cannot compare the same string ωω = abbabb  with the help of a stack.

Now we can’t compare symbol ‘a’ with the same symbol ‘a’ at the time of pop in stack method. So, it does not follow the stack method (LIFO).

Even if we want to try to use stack to identify the given language then it will never clear push and pop.

So, still, this given language has one infinite comparison but it is not possible to process by stack (LIFO)

Now, as we know one infinite comparison which is not possible by stack is a Context-Sensitive Language (CSL).

So, we can solve it by Tape.

Two more similar example

In the previous example Special  Cases: Examples we already discussed that two or more languages may look similar but the range of symbols which is present string like ω, can change the type of language. 

We know any language which has a finite range i.e. finite language is obviously Regular Language. 

And this language has only two strings L = {aa, bb}

And 

This language is similar to

But it does not change the type of the language.

So, any language L = ωω where ω is infinite then it is CSL.