Mathematical Foundation of Computer Science

REGULAR EXPRESSIONS

9.1 Introduction to Regular Expressions.............................................................................

9.2 Definition of Regular Expression...................................................................................

9.3 Equivalence of Regular Expression and Finite Automata

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

9.4.1 Construction of DFA from Regular Expression................................................

9.4 Finite Automata to Regular Expression

9.4.1 Construction of DFA from Regular Expression

9.5 Construction of Regular Expression from DFA

9.6 Finite Automatons with Output

9.6.1 M elay Automaton

9.6.1.1 Definition

9.6.1.2 R epresentation of Melay Automaton

9.6.1.3 Examples

9.6.2 Moore Automaton

9.6.2.1 Definition

9.6.2.2 R epresentation of Moore Automaton

9.6.2.3 Examples

9.7 Equivalence of Melay & Moore Automatons

9.7.1 Equivalent Machine Construction

(From Moore Machine-to-Melay Machine)

9.7.2 Mel ay Machine-to-Moore Machine

Exercises