Posts

Showing posts from December 2, 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.