Kleene’s Theorem

Q. 1: Does Kleene Theoram only restricted to Turing Machine?

Answer:

Kleene Theoram is primarily for Turing Machines only, but some similar self reference concepts can be formed in other machine models also.

Q. 2: Is it possible to implement Kleene Theoram practically?

Answer:

Kleene Theoram is basically a theoretical concept that does not have any direct practical applications. Computer Scientists understand the boundations, limitations with respect to this algorithm.

Q. 3: Is there any relation between Kleene Theoram and Halting Algorithm?

Answer:

Kleene Theoram and Halting Problem are closely related to each other as these both concepts involve self-reference and highlight the algorithmic solution limitation.

A language is said to be regular if it can be represented by using Finite Automata or if a Regular Expression can be generated for it. This definition leads us to the general definition that; For every Regular Expression corresponding to the language, a Finite Automata can be generated.

For certain expressions like:- (a+b), ab, (a+b)*; It’s fairly easier to make the Finite Automata by just intuition as shown below. The problem arises when we are provided with a longer Regular Expression. This brings about the need for a systematic approach towards Finite Automata generation, which Kleene has put forward in Kleene’s Theorem.

For any Regular Expression r that represents Language L(r), there is a Finite Automata that accepts same language.

To understand Kleene’s Theorem-I, Let’s take into account the basic definition of Regular Expression where we observe that , and a single input symbol “a” can be included in a Regular Language and the corresponding operations that can be performed by the combination of these are: Say, and be two regular expressions. Then,

1. +is a regular expression too, whose corresponding language is L() U L()
2. .is a regular expression too, whose corresponding language is L().L()
3. * is a regular expression too, whose corresponding language is L()*