ON THE SYNTHESIS OF FINITE-STATE ACCEPTORS

Abstract

Two algorithms are presented for solving the following problem: given a finite-set S of strings of symbols, find a finite-state machine which will accept the strings of S and possibly some additional strings which 'resemble' those of S. The approach used is to directly construct the states and transitions of the acceptor machine from the string information. The algorithms include a parameter which enable one to increase the exactness of the resulting machine's behavior as much as desired by increasing the number of states in the machine. The properties of the algorithms are presented and illustrated with a number of examples. The paper gives a method for identifying a finite-state language from a randomly chosen finite subset of the language if the subset is large enough and if a bound is known on the number of states required to recognize the language. Finally, some of the uses of the algorithms and their relationship to the problem of grammatical inference are discussed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1970
Accession Number
AD0708080

Entities

People

  • Alan W. Biermann
  • Jerome A. Feldman

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Alphabets
  • Artificial Intelligence
  • Automata
  • Automata Theory
  • Computer Science
  • Construction
  • Diagrams
  • Language
  • Machines
  • New York
  • Precision
  • Switching
  • Switching Circuits
  • Transitions

Readers

  • Computational Linguistics
  • Linear Algebra

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Machine Translation