Аннотация:
Описан способ построения по грамматике Ламбека с одним делением контекстно-свободной грамматики, задающей тот же язык, размер которой ограничен полиномом от размера исходной грамматики. Известные ранее конструкции Бушковского и Пентуса приводили к экспоненциальному росту размера грамматики.
Ключевые слова:формальные грамматики, исчисление Ламбека, конечные автоматы, сети доказательства.
Полный текст:
PDF файл (220 kB)