FOR FREE CONTENT

Some Examples 

If we see properly the language there are two conditions and between the two conditions, there is a ‘AND’.

So, ‘AND’ means you must follow two conditions at a time because we know the property of ‘AND’ if both conditions are true then the total condition will true. 

Here it is two conditions at a time and Context-Sensitive Language (CSL) can only work with two infinite conditions at a time.

So, it is CSL but not NCFL (Non-Deterministic Context-Free Language).

Note: Any language where two conditions are present with ‘AND’ then we treated as there are two conditions at a time and it is CSL.

This language is almost the same as the above language. Two conditions and in-between ‘AND’ so, there are two conditions at a time.

From this definition of language, it is clear that there is only one condition. If the number of a’s not equal to the number of b’s in a string, then it is accepted.

Now check for push and pop clear or not.

Either the stack is not empty or input is not empty after we push the same symbol and if we get the opposite symbol then we pop it then the string is accepted. So, there is one comparison and push, pop is cleared. 

So, it can be done by single stack and push, pop clear. 

One infinite condition and push, pop is cleared 

So, it is Deterministic Context-Free Language (DCFL) but not Regular Language.  

This language also has two conditions but here in between two conditions ‘OR’ operator is present. As we know the property of ‘OR’if any one of the conditions is true then it will true.

So, though there are two conditions it is not at a time.

Two conditions but not at a time i.e. it can be solved by one after another so, it will be executed by Push Down Automata.

But Non-Deterministic Push Down Automata (Language: NCFL) because by single stack is not possible to solve two conditions one after another, we need multiple stacks. Here two machines work for two conditions i.e. it creates two copies of the machine.

Only, NCFL works with multiple stacks where DCFL with a single stack.

We have already seen the same type of language in example1 and 2 that is two conditions operated by the ‘AND’ operator means two conditions at a time.

CSL can only work with two conditions at a time.