The Structure and Behavior of Finite Automata

J. Richard Büchi and Dirk Siefkes
Additional contact information
J. Richard Büchi: Purdue University, Computer Science Department
Dirk Siefkes: Technische Universität Berlin, Fachbereich Informatik

Chapter Chapter 3 in Finite Automata, Their Algebras and Grammars, 1989, pp 106-132 from Springer

Abstract: Abstract At the beginning of chapter 2 we proposed that finite k-algebra is one way of interpreting the intuitive idea of deterministic sequential system, as described in the introduction. In fact, it is clear how k-algebras make precise such ideas as input channel and internal configuration; a finite k-algebra (given by a table, transition graph, or transition tree) fully describes the internal response, to input stimuli, of a deterministic sequential system. However, we are left to make provisions for output of stimuli from the system to the environment. This is the subject of the present chapter, where we will introduce outputs g of a finite k-algebra A, to complete the rigorous definition of deterministic sequential systems. The resulting systems are called finite automata. We will study their structure and oppose this idea to that of behavior. The black-box behavior (or input-to-output behavior) tells how the system translates input stimuli to output stimuli and can be tested even when we have no access to the internal structure of the system. In contrast, the box will have to be worked on (with a screw driver or a can opener) if it is to reveal its structure .

Date: 1989
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-8853-1_3

Ordering information: This item can be ordered from
http://www.springer.com/9781461388531

DOI: 10.1007/978-1-4613-8853-1_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().