FOR FREE CONTENT

How to identify language 

Before we identify the language first we see the type of memory contain by different machines because machines can be differentiated only by the type of memory.

If we design a Finite Automata or if we write regular expression for it then it is a regular language.

It has infinite tape. 

Example:

So, ordering is done by Finite Automata with finite memory and we can write a Regular Expression.

So, the above machine is a finite automata and language is a regular language.

Now we consider one language like 

Now this problem is not solved by Finite Automata because infinite comparison is not possible by Finite Automata with finite memory. 

Note: Finite Automata perform comparison but finite comparison but in case of infinite comparison, it is not to be done because of finite memory.

Example:

It is a regular language because here is a comparison but the range of n is finite so, it is a finite comparison. 

Example:

It is not a regular language because here it is an infinite comparison which not possible by finite automata with finite memory.

We know we cannot solve it by Finite Automata but it is solved by Push Down Automata (PDA). 

So, one infinite comparison is solved by stack if it is in LIFO order (at a time one comparison).

But one comparison but not follow LIFO order or more than one comparison then it will be solved by infinite tape (Context Sensitive Language) (at a time more than one comparison).

Example: 

Let us take a sample string of the given language 

Whenever we get ‘a’ push on top of the stack and we delete (pop) ‘a’ from stack whenever we will get ‘b’ as an input. 

So, there is no problem, push and pop us clear means it is done by a single copy of stack then we can say it is Deterministic Context Free Language (DCFL)

In DCFL, push or pop should be cleared (single copy of stack).

If push or pop is not cleared (Not possible by a single copy of stack) then it creates multiple copies of the stack so, in this is the case it is not DCFL.

Another ω = aabb is DCFL because here push and pop are cleared.

Because given language is 

So, the number of ‘a’ push on the stack and the number of ’b’ which pop ‘a’ should be equal but here input ‘a’ on the stack still present but input b is empty. So, the string is accepted if after process stack is empty.

Important points to identify languages: 

1. Finite Automata (Language: Regular Language) can work with finite comparison. 

Regular Language cannot work with infinite comparison.

2. Deterministic Push Down Automata (Language: DCFL) can work with one infinite comparison but in LIFO ORDER (at a time one comparison) and push & pop must be clear (single copy of stack).

DCFL cannot work with more than one comparison and multi-copy of the stack. 

3. Non Deterministic Push Down Automata (Language: NCFL) can work with one infinite comparison but is also work with multiple copies of the stack. 

NCFL cannot work with more than one comparison.

4. Linear Bounded Automata (Language: CSL) can work with more than one infinite comparison and one infinite comparison but not follow LIFO ORDER (at a time more than one comparison).