Утверждение: Любой язык, построенный в алгебре регулярных событий (заданный регулярным событием) является языком порождаемым регулярной грамматикой.
Доказательство: А) Пусть заданы два события и над алфавитом . Элементарные события — это всевозможные знаки принадлежащие .
В)Представим основные операции над событием в виде продукций регулярной грамматики, зная или предполагая, что существуют регулярные грамматики порождающие и . В случае элементарных языков это очевидно, что , тогда грамматикой порождающей этот язык является .
С) Операция объединения языков . Зная грамматики содержащие и , где и . Построим грамматику такую что , очевидно, что для этой грамматики , а множество нетерминальных знаков .
D) Конкатенация двух языков .
Существует ли регулярная грамматика, которая порождает конкатенацию двух языков, если известно, что каждый язык порождается регулярной грамматикой. В этом случае определим как , где продукции вида такие что , , изменяем и приводим к виду и получим грамматику которая содержит объединение нетерминальных знаков первой и второй грамматик. Построим множество продукций и аксиому . В результате видно, что любой вывод строки начинается с строки языка , а по завершению вывода в начинается вывод в и порождается суффикс строки .
Е) Итерация языков .
Строим грамматику которая имеет тот же алфавит терминальных знаков (они остаются те же), а множество продукций будет следующим: , где — это множество продукций преобразованных ана¬логично пункту D, используя вместо аксиому , .
F) Если выбрать в качестве исходных языков элементарные события, которые порождаются регулярной грамматикой, то любое регулярное выражение представляет собой регулярный язык.