---
title: "Grammatical Inference on the Basis of Linear Environments of Symbol Strings"
authors:
  - "Yoshiyuki Kotani"
doi: ""
url: "https://ijcai.org/proceedings/1979/110"
pdf: "https://ijcai.org/proceedings/1979/0110.pdf"
venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence"
year: 1979
pages: ""
track: ""
keywords:
---

# Grammatical Inference on the Basis of Linear Environments of Symbol Strings

Yoshiyuki Kotani

*Proceedings of the Sixth International Joint Conference on Artificial Intelligence*.

## Abstract

A new method of grammatical inference is proposed. The inference procedure, receiving only positive sample sentences, produces a grammar. A notion of "bounded context" is introduced which represents linear environment of a string in sample sentences. The procedure consists of (1) calculating the bounded context of strings, (2) finding a pair of context-equivalent strings, (3) reducing the sample sentences by means of the pair, and (4) iterating (1) to (3) until there is no pair of context-equivalent strings in the reduced sample sentences. The output grammar is constructed from the reduced sentences and the pairs of strines obtained in " (2). Sample sentences are grammatically correct with respect to the grammar inferred from the sentences. All of regular languages and a number of non-trivial context-free languages are inferred correctly by the method, when sufficient but a finite number of sample sentences are given.