Finite automata and applications

Loading...
Thumbnail Image
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
Description
Keywords
Citation