Saturday, December 8, 2012

Kleene's Theorem : Applications

Kleene's Theorem :

Part - I :

"Any Regular Language can be Accepted by a Finite Automaton"

Application:

The Construction in the proof of above theorem provide an algorithm for constructing an NFA-^ corresponding to a given Regular Expression.

If we have NFA-^, M1 and M2, the proof of above theorem provide us with algorithms for constructing new NFA-^ to recognize the Union, Concatenation, and Kleene * of the Corresponding Languages.

Part-II:

"The Language Accepted by any Finite Automaton is Regular"

Application:

The Construction in the proof of above theorem provides way to find a Regular Expression Corresponding to a given Finite Automaton.