COMPILER DESIGN

Detailed explanation-1: -Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene’s theorem (after American mathematician Stephen Cole Kleene).

Detailed explanation-2: -The two finite automata (FA) are said to be equivalent if both the automata accept the same set of strings over an input set . When two FA’s are equivalent then, there is some string x over . On acceptance of that string, if one FA reaches to the final state, the other FA also reaches to the final state.

Detailed explanation-3: -Regular expressions and finite automata are equivalent in their descriptive power. Any regular expression can be converted into a finite automaton that recognizes the language it describes, and vice versa. Theorem. A language is recognizable by a FA if and only if some regular expression describes it.

Detailed explanation-4: -Finite automata represent exactly regular languages, and another way to describe regular languages is through regular expressions. As an example, (deterministic) finite automata can accept all and only the strings of 0’s and 1’s that have the sequence 01 somewhere in the string.