DOI

The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of Σ* a* obey a certain periodicity property, which, in particular, makes the language {anb2n | n ≥ 0} nonrepresentable. It is also shown that {anbncs | n ≥ 0, s ∈ {a, b}} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate {anb nc* |n ≥S 0}.

Язык оригиналаанглийский
Название основной публикацииFundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings
ИздательSpringer Nature
Страницы446-457
Число страниц12
ISBN (печатное издание)9783540742395
DOI
СостояниеОпубликовано - 2007
Опубликовано для внешнего пользованияДа
Событие16th International Symposium on Fundamentals of Computation Theory, FCT 2007 - Budapest, Венгрия
Продолжительность: 27 авг 200730 авг 2007

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том4639 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция16th International Symposium on Fundamentals of Computation Theory, FCT 2007
Страна/TерриторияВенгрия
ГородBudapest
Период27/08/0730/08/07

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 78926537