Finite state automata and regular languages.

Abstract

This thesis is intended for an audience familiar with basic formal language theory and finite state automata theory. Chapter 1 is the introduction to regular languages and the operations among them. Chapter 2 is the introduction to deterministic finite state automata and their computation. Chapter 3 is the introduction to nondeterministic finite state automata and shows the equivalence of deterministic finite state automata and nondeterministic finite state automata. Chapter 4 proves the famous Kleen's Theorem and builds up the relationship between regular languages and finite state automata. Chapter 5 discusses the minimization of deterministic finite state automata. Chapter 6 summarizes the thesis.