Автоматные грамматики, регулярные выражения являются эквивалетными способами задания автоматных языков. Регулярные выражения имеют то важное достоинство, что

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

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

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

 

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

При использовании пораждающих грамматик итераци задаются с помощью рекурсии.

 

Регулярное выражение над алфавитом Е- это цепочка символов в расширенном алфавите ЕU{+,*,(,)} множество всех таких цепочек вырожений образует язык.

 

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

S:= a|SS|S*|S+S|(s)|E

В этой записи а-это любой символ из алфавита Е.