Learning Simple Deterministic Languages
Abstract
This paper is concerned with the problem of learning simple deterministic languages. The algorithm described in this paper is essentially based on the theory of model inference given by Shapiro. In our setting, however, nonterminal membership queries, for nonterminals except the start symbol, are not used. Instead of them, extended equivalence queries are used. Nonterminals that are necessary for a correct grammar and their meanings are introduced automatically. We show an algorithm that, for any simple deterministic language L, outputs a grammar G in 2-standard form, such that L = L(G), using membership and extended equivalence queries. We also show that the algorithm runs in time polynomial in the length of the longest counterexample and the minimum number of nonterminals of a correct grammar.
Cite
Text
Ishizaka. "Learning Simple Deterministic Languages." Annual Conference on Computational Learning Theory, 1989. doi:10.1016/B978-0-08-094829-4.50014-3Markdown
[Ishizaka. "Learning Simple Deterministic Languages." Annual Conference on Computational Learning Theory, 1989.](https://mlanthology.org/colt/1989/ishizaka1989colt-learning/) doi:10.1016/B978-0-08-094829-4.50014-3BibTeX
@inproceedings{ishizaka1989colt-learning,
title = {{Learning Simple Deterministic Languages}},
author = {Ishizaka, Hiroki},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1989},
pages = {162-174},
doi = {10.1016/B978-0-08-094829-4.50014-3},
url = {https://mlanthology.org/colt/1989/ishizaka1989colt-learning/}
}