COMPILER DESIGN

Detailed explanation-1: -Regular expressions and finite automata have equivalent expressive power: For every regular expression R, there is a corresponding FA that accepts the set of strings generated by R. For every FA A there is a corresponding regular expression that generates the set of strings accepted by A.

Detailed explanation-2: -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-3: -Regular expression is the language which is used to describe the language and is accepted by finite automata. Regular expressions are the most effective way to represent any language. Let be an alphabet which denotes the input set. is a regular expression which denotes the empty set.

Detailed explanation-4: -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-5: -For Every Regular Expression There is a Corresponding FSM Clearly we can construct an FSM for any finite language, and thus for ∅ and all the singleton strings.