Learning of Construction of Finite Automata from Examples Using Hill- Climbing. RR: Regular Set Recognizer

Abstract

The problem addressed in this paper is heuristically-guided learning of finite automata from examples. Given positive sample strings and negative sample strings, a finite automaton is generated and incrementally refined to accept all positive samples but do no negative samples. This paper describes some experiments in applying hill-climbing to modify finite automata to accept a desired regular language. We show that many problems can be solved by this simple method. We then describe the method how to 're-construct' a finite automaton if the positive and/or negative samples are slightly altered, without starting from the beginning. Finally, we have an actual system. RR: Regular set Recognizer, that learns to recognize a regular set from the samples that are given by a human teacher one by one.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1982
Accession Number
ADA120123

Entities

People

  • Masaru Tomita

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Automata
  • Automata Theory
  • Automatic Programming
  • Climbing
  • Cognitive Science
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Construction
  • Inverse Problems
  • Language
  • Machines
  • Mass Spectrometry
  • New York

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Artificial Intelligence
  • Regression Analysis.