Language Identify: Examples


Note: All examples of language identification are very important because this is a very vital chapter and lots of questions have been asked in the examination. (UGC NET, GATE, BTech, B.Sc, M.Sc, Mtech, and other examinations).


Some Important Examples:




Because Finite Automata can perform infinite ordering but not perform the infinite comparison. In this language, there is no comparison only ordering



We know for the infinite ordering problem can be solved by Finite Automata. 



There is one comparison but it is finite time


It has one infinite comparison and as we know Finite Automata (FA) cannot work with infinite comparison. 

But we can solve it by Push Down Automata (PDA) because we know PDA can work with one infinite comparison with the infinite stack. In fact, it is Deterministic Push Down Automata (DPDAbecause of push and pop are clear here


Here ‘m’ is equal to ‘n’ or greater than ‘n’.


In this condition, the string will be accepted either empty stack and empty inputs or empty stack but inputs are present


Where n = m and b is extra or left after the stack is empty in option 1 where m > n





Regular Language is not able to work with infinite time comparison. 

As we know PDA can work with one infinite time comparison. 

Even it is a DPDA because push and pop are cleared means by a single stack we can solve our problem. String accepted when after operation stack is empty in this case.


So, stack clear and string accepted.