Abstract: В работе исследуется вопрос моделирования форм Бэкуса-Наура (BNF-систем), а также порождающих грамматик с помощью GNF-систем. GNF-системы являются базой для построения монотонных операторов таких, что наименьшие неподвижные точки этих операторов являются полиномиально вычислимыми. В данной работе результаты, полученные с помощью построения подходящих GNF-систем и применения к ним обобщенного полиномиального аналога теоремы Ганди о неподвижной точке, смогли дать ответы на вопросы существования полиномиально вычислимого представления для множества выводов в порождающих грамматиках. Более того, было показано, что если GNF-система моделирует BNF-систему, то множество прообразов в GNF-системе для множества представлений любого нетерминального символа в BNF-системе также является полиномиально вычислимым. Этот результат сразу позволяет перекодировать все определяемые конструкции в BNF-системе, в том числе синтаксис программ высокоуровневых языков программирования так, что они становятся распознаваемые за полиномиальное время.

Cite: Нечёсов А.В.
Некоторые вопросы полиномиально вычислимых представлений для порождающих грамматик и форм Бэкуса-Наура
Математические труды. 2022. Т.25. №1. С.134-151. DOI: 10.33048/mattrudy.2022.25.106 РИНЦ

Translated: Nechesov A.V.
Some Questions on Polynomially Computable Representations for Generating Grammars and Backus–Naur Forms.
Siberian Advances in Mathematics. 2022. V.32. P.299–309. DOI: 10.1134/S1055134422040058 Scopus РИНЦ OpenAlex

Dates:

Submitted:	Feb 22, 2022
Accepted:	May 12, 2022
Published print:	Jun 30, 2022
Published online:	Jun 30, 2022

Identifiers:

≡ Elibrary:

50047164

Altmetrics: