Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
The paper studies the family of Boolean LL languages, generated by Boolean grammars and usable with the recursive descent parsing. It is demonstrated that over a one-letter alphabet, these languages are always regular, while Boolean LL subsets of Σ*a* obey a certain periodicity property, which, in particular, makes the language anb2n|n0 non-representable. It is also shown that linear conjunctive LL grammars cannot generate any language of the form L·a,b, with L non-regular, and that no languages of the form L·c*, with non-regular L, can be generated by any linear Boolean LL grammars. These results are used to establish a detailed hierarchy and closure properties of these and related families of formal languages.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 5132-5155 |
Число страниц | 24 |
Журнал | Theoretical Computer Science |
Том | 412 |
Номер выпуска | 39 |
DOI | |
Состояние | Опубликовано - 9 сен 2011 |
ID: 41140892