6.2. Некоторые понятия теории формальных языков

Развитая к настоящему моменту теория языков сетей Петри подобна другим частям теории формальных языков. Классическая теория формальных языков представлена в нескольких монографиях [130, 265, 99]. Многие из основных понятий теории языков сетей Петри заимствованы из классической теории формальных языков.

Алфавит — это конечное множество символов. Строка — любая последовательность конечной длины из символов алфавита. Пустая стоока это строка, не имеющая символов, т. е. нулевой длины. Если алфавит, то множество всех строк из символов включая пустую строку. является множеством всех непустых строк над алфавитом

Языком называется множество строк над алфавитом. В общем случае языки могут быть бесконечными, следовательно, одной из проблем является представление языка. Для представления языков было предложено два подхода. Один заключается в определении машины, которая порождает строку из языка, и любая строка из языка порождается ею. Другой подход подразумевает определение грамматики, которое указывает, как последовательным применением ее правил порождения получаются строки языка.

Ограничения, накладываемые на вид машин или грамматик, порождающих языки, определяют классы языков. Традиционными классами языков являются: регулярный, контекстно-свободный, контекстно-связанный и языки типа 0, соответствующие конечным автоматам, магазинным автоматам, линейно-ограниченным автоматам и машинам Тьюринга. Каждый из классов языков порождается соответствующим классом автоматов. Это дает прекрасные средства для установления связи теории сетей Петри с теорией формальных языков: мы определяем класс языков сетей Петри как класс языков, порождаемых сетями Петри. Детали этого определения аналогичны деталям определения любого другого класса языков.

Рассмотрим в качестве примера конечные автоматы и регулярные выражения. Конечный автомат С есть пятерка где конечное множество состояний, алфавит символов, функция переходов, начальное

состояние, конечное множество заключительных состояний. Функция переходов естественным образом обобщается на случай отображения из Язык порождаемый конечным - это множество строк над определяемое следующим образом:

Всякому конечному автомату соответствует язык, а класс всех языков, порождаемых конечными автоматами, называется классом регулярных языков. Конечный автомат определяется своим языком. Если два конечных автомата имеют одинаковые языки, они эквивалентны.