Source:
ICGI 2010, Springer, Valencia (2010)
Abstract:
In this paper we present two hierarchies of context-free languages: the $k,l$-NTS languages and the $k,l$-NTS$^\leq$ languages. $k,l$-NTS languages generalize the concept of Non-Terminally Separated (NTS) languages by adding a fixed size context to the constituents, as $k,l$-substitutable languages generalize substitutable languages. $k,l$-NTS$^\leq$ languages are $k,l$-NTS languages that also consider the edges of sentences as possible contexts. We then prove that Unambiguous $k,l$-NTS$^\leq$ ($k,l$-UNTS$^\leq$) languages be converted to plain old UNTS languages over a richer alphabet. Using this and the result of polynomial PAC-learnability with positive data of UNTS grammars proved by Clark, we prove that $k,l$-UNTS$^\leq$ languages are also PAC-learnable under the same conditions.
