Применение сетей Петри для анализа КС-грамматик

Abstract

Предложена схема использования сетей Петри для исследования некоторых свойств КС-грамматик. Метод позволяет, в частности, исследовать заданную КС-грамматику на пустоту и конечность порождаемого языка, используя дерево покрываемости соответствующей сети Петри. Кроме того, предложенный метод позволяет сформулировать необходимые условия порождения заданного слова КС-грамматикой в терминах матричного анализа соответствующей сети.

Запропоновано схему використання мереж Петрі для дослідження деяких властивостей КВ-граматик. Метод дозволяє, зокрема, досліджувати задану КВ-граматику на порожність та скінченність породжуваної мови, використовуючи дерево покриття відповідної мережі Петрі. Крім того, запропонований метод дозволяє сформулювати необхідні умови породження заданого слова КВ-граматикою в термінах матричного аналізу відповідної мережі.

The scheme of the use of Petri nets for the study of some properties of the CF-grammars is proposed. This method, enables, in particular, to investigate the emptiness and finiteness of language, generated by given CF-grammar, using tree cover of the relevant Petri net. Additionally, the proposed method allows to formulate the necessary conditions for the generation of a given word by CF-grammar in terms of a matrix analysis of the relevant network.