Book contents
- Frontmatter
- Contents
- Preface
- Part 1 Preliminaries
- Part 2 Combinational logic
- Part 3 Finite-state machines
- 9 Introduction to synchronous sequential circuits and iterative networks
- 10 Capabilities, minimization, and transformation of sequential machines
- 11 Asynchronous sequential circuits
- 12 Structure of sequential machines
- 13 State-identification experiments and testing of sequential circuits
- 14 Memory, definiteness, and information losslessness of finite automata
- 15 Linear sequential machines
- 16 Finite-state recognizers
- Index
16 - Finite-state recognizers
from Part 3 - Finite-state machines
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Part 1 Preliminaries
- Part 2 Combinational logic
- Part 3 Finite-state machines
- 9 Introduction to synchronous sequential circuits and iterative networks
- 10 Capabilities, minimization, and transformation of sequential machines
- 11 Asynchronous sequential circuits
- 12 Structure of sequential machines
- 13 State-identification experiments and testing of sequential circuits
- 14 Memory, definiteness, and information losslessness of finite automata
- 15 Linear sequential machines
- 16 Finite-state recognizers
- Index
Summary
In this chapter we consider the characterization of finite-state machines and the sets of sequences that they accept. We investigate a number of generalized forms of finite-state machines and prove that these forms are equivalent, with respect to the sets of sequences that they accept, to the basic deterministic finite-state model. In Sections 16.2 and 16.3 we study the properties of nondeterministic state diagrams, called transition graphs, which will prove to be a useful tool in the study of regular expressions. Procedures are developed whereby any transition graph can be converted into a deterministic state diagram.
Section 16.4 presents the language of regular expressions, which provides a precise characterization of the sets of sequences accepted by finite-state machines. In the following two sections we prove that any finite-state machine can be characterized by a regular expression and that every regular expression can be realized by a finite-state machine. Finally, in Section 16.7 we will be concerned with a generalized form of finite-state machines known as two-way machines.
Deterministic recognizers
So far, we have regarded a finite-state machine as a transducer that transforms input sequences into output sequences. In this chapter we shall view a machine as a recognizer that classifies input strings into two classes, those that it accepts and those that it rejects. The set consisting of all the strings that a given machine accepts is said to be recognized by that machine.
- Type
- Chapter
- Information
- Switching and Finite Automata Theory , pp. 570 - 607Publisher: Cambridge University PressPrint publication year: 2009