Эквивалентность регулярных выражений и автоматных грамматик

Автоматные языки являются регулярными множествами. Регулярные множества являются автоматными языками.

Сказанное означает, что для любой автоматной грамматики можно записать такое регулярное выражение, что обозначаемое этим выражением множество цепочек совпадает с языком, порождаемым грамматикой.

И, наоборот, для любого регулярного выражения можно найти автоматную грамматику, порождающую то же множество цепочек, что и регулярное выражение.

Будем считать, что автоматный язык задается синтаксической диаграммой. Можно установить взаимно однозначное соответствие между конструкциями, из которых строятся регулярные выражения (правила 1-6) и фрагментами, из которых состоят синтаксические диаграммы автоматных грамматик.

Это соответствие показано в табл. 2.

Таблица 2. Эквивалентность регулярных выражений и автоматных грамматик

Используя такое соответствие, по выражению можно построить диаграмму, а по диаграмме — регулярное выражение. Уточнение деталей таких построений, которым мы не будем здесь заниматься, и доказывает справедливость сформулированного ранее утверждения об эквивалентности.

Уместно напомнить, что автоматные грамматики называют также регулярными.