On Learning A Class of Context-free Languages in Polynomial Time(Complexity Theory and Related Topics)
Takashi Yokomori · Institutional Repositories DataBase (IRDB) · 1990
The problem of learning context-free languages is studied, in which a subclass called c-deterministic context-free languages is introduced.The class of c-deterministic context-free languages properly contains the class of regular sets.It is shown that the class of c-deterministic context-free languages is learnable in polynomial time from membership queries and equivalence queries, that is, it is polynomial time learnable from so-called minimally adequate teacher.