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

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

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

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

и фрагментами графов конечных автоматов

 

 

 

 

 

Используя это соответствие по выражению можно построить граф КА, а по графу - регулярное выражение.

ТЕОРЕМА) Язык допускается конечным автоматом тогдаи только тогда, когда он является регулярным множеством.