1. Регулярные языки и конечные автоматы. (та)

Согласно Хомскому регулярная грамматика - это грамматика, продукции которой имеют вид : а) А а | aB – правосторонняя; б) А а | Bа – левосторонняя; где a  V ; A ,B  W. Регулярные языки – это языки, порожденные регулярными грамматиками. Регулярная грамматика соответствует конечному автомату. Теорема. Для любого непустого языка L порождаемого регулярной грамматикой G₃, существует Конечный Автомат К, возможно недетерминированный, представляющий (порождающий и распознающий) язык L. Конечным автоматом называется формальная система К которая задается 5-ю объектами К=<A, Q, B, ,  >, где A - входной алфавит ={a₁, a₂, a₃, … , a_m}, Q - алфавит состояний {q₁, q₂, q₃, … , q_n}, B - выходной алфавит {b₁, b₂, b₃, ... , b _k}, - функция переходов; : QAQ;  - функция выходов автомата ; : QAB .

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов ,где S, X и Y — конечные непустые множества, а δ и λ — отображения вида: и со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата. Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата.

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y,

с зависимостью состояний и выходных сигналов во времени уравнением:

. Автоматом Мура называется конечный автомат, у которого функции выхода не зависят от входного знака (зависит только от состояния автомата).K=<A, Q, B,  >. Для любого q_i принадлежащего Q и для любого a_j1, a_j2 принадлежащего A. ( q_i, a_j1) = (q_i, a_j2) - это означает что функция  является одноаргументной функцией и зависит только лишь от состояния автомата. Обозначим эту функцию  Km=< A, Q, B, > ,  : Q  B (иногда  называют - функцией отметок). Состояние выхода можно записать в самой системе. Для любого автомата Мили К существует неотличимый от него автомат Мура Кm.