Abstract
Non-terminally separated (NTS) languages are a subclass of deterministic context free languages where there is a stable relationship between the substrings of the language and the non-terminals of the grammar. We show that when the distribution of samples is generated by a PCFG, based on the same grammar as the target language, the class of unambiguous NTS languages is PAC-learnable from positive data alone, with polynomial bounds on data and computation.
| Original language | Undefined/Unknown |
|---|---|
| Title of host publication | Proceedings of the 8th International Colloquium on Grammatical Inference (ICGI) |
| Pages | 59-71 |
| Number of pages | 13 |
| Volume | 4201 LNAI |
| Publication status | Published - 2006 |