Some Examples 


It is an infinite language but there is no infinite comparison because m + n = even it is not a comparison even we can write regular expression for this language.

We got even number by odd + odd or even + even.



If language 


This language is defined as the number of a’s and number b’s is equal in the string which accepted by this machine like 

It is clear that this language has one infinite comparison.


Now we check push and pop are cleared or not 

Let take an example

ω = aabbbbabaa. Here the number of a and b is the same.


If the stack is 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. 

It is a Deterministic Context-Free Language (DCFL), but not Regular Language.


There some more examples similar to the previous one:


From this language, it is clearly understood that there are two infinite comparisons at a time. The number of a’s equals the number of b’s and the number of b’s equal to the number of c’s.

Context-Sensitive Language (CSL) can only able work with two infinite comparisons at a time

As we know Context-Free Language (CFL) can work only with one infinite comparison at a time.


This language is the same as above. It has infinite comparison at a time.