Finite automata and applications
Loading...
Date
2010
Authors
R.F Elfakhakhre, Nawara
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A finite automaton can be considered as the simplest machine model in that the machine
has a finite memory; that is, the memory size is independent of the input length. Finite
automaton is the oldest model of formal language theory, since in 1943, in the
pioneering work of McCulloch and Pitts, the concept of automaton appeared as a model
for studying nervous systems. Then Kleene wrote the first paper on finite automata that
proved a theorem which we now know as Kleene's theorem. In 1959, Michael Rabin
and Dana Scott presented a study on the theory of finite automata, in their joint paper
"Finite Automata and Their Decision Problem", which introduced the idea of
nondeterministic machines, which has proved to be a very important concept. In the
early stage, the theory of finite automata has been developed as a mathematical theory
for sequential circuits. A sequential circuit maintains a current state from a finite number
of possible states. The circuit logic (which is a finite state control) decides the new state
based on the current state of the circuit and the given input symbol. Once an input
symbol is processed, the circuit will not be able to read it again.
A main application of finite automata is text processing. In compiler design, finite
automata are used to capture the logic of lexical analysis. Other applications include
string matching, natural language processing, text compression, etc.
In this project, we first introduce the concepts of finite automata and review the basic
definitions. Then we introduce the two types of finite automata deterministic finite
automata (DFA), nondeterministic finite automata (NFA). The two types of finite
automata really accept the same family of languages, the regular languages, that will
be introduced here, and then we describe the important Kleene's theorem in two parts.
Finally, we also introduce the basic definitions for fuzzy finite automata and regular
fuzzy languages as stated by (Salomma et.al (1995), Martin Vide et.al (2004)), which is
application of finite automata such as lexical analyser