Mathematical Foundation of Computer Science

DHARM

216 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

9.3 Equivalence of Regular Expression and Finite Automata...........................................

Every language which is accepted by either deterministic finite automaton (DFA) or
nondeterministic finite automaton (NFA) with or without ∈-moves is known as regular language.
It means that there exists a set of regular expressions that generates the strings of this class of
language. So, if a language is regular then certainly it can be expressed by regular expression/
s and conversely this language must be the out come from some finite automaton (Fig. 9.1).

Regular

Expression

Finite

Automata

Regular

Language

DFA NFA

NFA with

e-moves

Fig. 9.1

Alternatively we may say that,

I. A regular expression can be expressed in some form of finite automata either DFA/

NFA/NFA with ∈-moves (i.e., from Regular Expression to Finite Automata).

II. The acceptance power (language) of finite Automata can be expressed by regular

expression (i.e., from Finite automata to Regular Expression).

Now we study in detail about the points I and II such that the method of construction of

finite automaton from given regular expression and conversely the determination of regular

expression from finite automaton. What we have discuss so far it can be easily verified by

study of the following theorems.

9.3.1 Construction of NFA with ∈-moves from Regular Expression........................

Theorem 9.1. If r be a regular expression and its language is L(r) then there exists a NFA with

∈-moves N∈ i.e., L(N∈) = L(r).