Согласно Хомскому регулярная грамматика — это грамматика, продукции которой имеют вид :
а) А® а | aB – правосторонняя;
б) А® а | Bа – левосторонняя; где a ? V ; A ,B ? W
Регулярные языки – это языки, порожденные регулярными грамматиками. Регулярная грамматика соответствует конечному автомату.
Теорема 3.3. Для любого непустого языка L порождаемого регулярной грамматикой G3, существует КА К, возможно недетерминированный, представляющий ( порождающий и распознающий) язык L.
Конечным автоматом называется формальная система К которая задается 5-ю объектами К=<A, Q, B, d, l >, где A — входной алфавит ={a1, a2, a3, …, am}, Q — алфавит состояний {q1, q2, q3, …, qn}, B — выходной алфавит {b1, b2, b3, …, b k}, d — функция переходов; d: Q?A®Q ; l — функция выходов автомата ; l: Q?A®B .
Алгоритм Мили: (построение классов эквивалентности): Шаг1: Разбиваем множество состояний Q некоторого автомата K=<A, Q, B, d, l > на классы следующим образом. Два различных состояния q и q’ относим в один и тот же класс эквивалентности Ci1,если для всех a ? A, l(q, a) = l(q’ , a). Шаг i: Получено разбиение на n — классов эквивалентности . Шаг i+1 : Два состояния q и q’ из одного класса эквивалентности Cji относим в один класс Cji+1 , если для любого входного знака нашего автомата d(q, a) и d(q’ , a) ? одному и тому же классу. Иначе образуем новый класс CK+1i+1 куда заносим состояния q’ , а так же все остальные q из множества Cji для которых d(q, a) и d(q’ , a) принадлежат одному классу. Условие завершения процедуры : Если на i+1 шаге получим разбиение, которое не уменьшилось по отношению к i шагу .
Автоматом Мура называется конечный автомат, у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).K=<A, Q, B, d, l >. Для любого qi принадлежащего Q и для любого aj1, aj2 принадлежащего A. l( qi, aj1) = l (qi, aj2) — это означает что функция l является одноаргументной функцией и зависит только лишь от состояния автомата. Обозначим эту функцию m. Km=< A, Q, B, d, m > , m : Q ® B (иногда m называют — функцией отметок). Состояние выхода можно записать в самой системе.
