Вопрос 33. Конечный автомат и регулярные языки.
Теорема 3.6 «О конечных автоматах и регулярных языках»
Для любого языка, заданного регулярной грамматикой существует конечный автомат возможно недетерминированный, принимающий множество строк, совпадающих с этим языком. Верна и обратная: для любого конечного автомата множество принимаемых им строк может быть описано регулярной грамматикой.
Док-во:
1)Задана регулярная грамматика G3=<V,W,P,I>. Построим конечный автомат, который распознает или порождает строки языка L порожденного некоторой регулярной грамматикой G3. Введем множество состояний Q состоящее из нетерминальных знаков грамматики и дополненное нетерминальным знаком W0. Q={W1,W2,…,Wn,W0} , Wi принадлежат W. Продукции грамматики G3 дополним продукцией P=PU{W0->e} а продукции вида A->b заменим на продукции A->bW0 получим в результате грамматику эквивалентную исходной. Входной алфавит автомата определим как алфавит терминальных знаков грамматики. A=V, B={0}. Если имеется продукция Pi: Wi->aWj то ведем дугу от узла Wi к узлу Wj и помечаем дугу знаком 0. Wia->Wj
Построенный таким образом автомат распознает тот же язык что и порождает грамматика G3. Действительно все строки, порождаемые грамматикой G3 принимаются автоматом K что видно из построения.
2) Построим конечный автомат порождающий строки языка порожденного грамматикой G3. L(G3), K=<A,Q,B,sigma,lambda>
A={0} , B=V , Q=WU{W0}
sigma: Wie->Wj , P: Wi->bWj
lambda: Wie->b , P: Wie->Wjb
Очевидно что построенный автомат порождает тот же язык что и регулярная грамматика.
3)Пусть задан конечный автомат K=<A,Q,B,P,I> , A={a1,…,am} — входной алфавит B={b1,…,bk} — выходной алфавит Q={q0,q1,…,qn} — множество состояний P: QxA->QxB Построим грамматику по заданному конечному автомату:
а) Автомат акцептор. В этом случае у нас нет выходной очереди. B={e} , P:QxA->Q. Построим грамматику так- поставим в соответствие каждому qi нетерминальный знак грамматики Аi. Если отображению Р принадлежит команда qiak->q0 то добавляем продукцию Ai->ak, в качестве аксиомы грамматики выбираем знак A1 соответствующий начальному состоянию автоматов.
б) Порождающий автомат. А={e}, P:Q->QxB. Поставим в соответствие каждому состоянию qi нетерминальный знак грамматики Ai (qi<->Ai). Если имеется команда qi->qjbk то к продукциям грамматики добавляем следующую продукцию Ai->bkA, если имеется команда qi->q0bk то добавляем Ai->bk , в качестве аксиомы выбираем знак А1 соответствующий начальному состоянию автомата.
Заключение: В случаях а) и б) мы построили грамматику G3=<A,W,P`,A1> , G3=<B,W,P~,A1> , где А-входной алфавит, B-выходной алфавит автомата , W- нетерминальные знаки грамматики, W={Ai | qi принадлежит Q, i=1…n} , P` и P~ построены соответственно в пунктах 1) и 3).

Вопрос 34. Конечный автомат. Задание функций на множестве строк. Автоматное отображение. Свойства автоматного отображения.
Конечным автоматом называется формальная система К которая задается 5-ю объектами К=<A, Q, B, ?, ? >, где A — входной алфавит ={a1, a2, a3, …, am}, Q — алфавит состояний {q1, q2, q3, …, qn}, B — выходной алфавит {b1, b2, b3, …, b k}, ? — функция переходов; ?: Q?A?Q ; ? — функция выходов автомата ; ?: Q?A?B . Мы разбили Р3 на 2 независимых отображения.
Задание функций на множестве строк. Для любого автомата K=<A,Q,B,?,?> функции ? и ? могут быть заданы на множестве строк A+. Пусть есть некоторая строка ? состоящая из k знаков. Используем индуктивные задания функций ? и ?. а) ?(qi, aj) находим из автоматной таблицы. ?(qi, aj) находим из автоматной таблицы. б) для любой строки ? ? A+ и любого знака aj можно записать: ?(qi , ? aj ) = ?(?(qi, ?),aj); ?(qi, ? aj ) = ?(?(qi, ?), aj).
Автоматное отображение (автоматный оператор) — это соответствие, отображающее входные строки конечного автомата в выходные строки. К: А+?B+ ; K(qi, ?) = ? , ??A+, ??B+ K(?)=? —КА перерабатывает строку ? в ?, qi — не указывается, когда неважно начальное состояние. Автоматное отображение можно рассматривать как функцию на множестве входных строк и принимающих значение из множества выходных строк.
Условие полноты — для любого входного знака и для любого состояния существует некоторые следующие состояния автомата. (не для любого qi существует Q и не для любого aj существует A)
Условие непротиворечивости — для любого состояния, любого входного знака существует единственное следующее состояние.

Вопрос 35. Изоморфизм и гомоморфизм конечных автоматов. Неотличимые состояния и неотличимые автоматы.
Гомоморфизм автоматов К¬1 и К2 — тройка отображений (функций) f, g, h, которые задают: f: А1?А2 ; g: Q1?Q2 ; h: B1?B2 , и если для любых a, q, b, ? A, Q, B, то { ? ?2(g(q), f(a)) = g(?1(q, a)); ? ?2(g(q), f(a))=h(?1(q, a)). По смыслу, гомоморфизм — переименование алфавитов конечных автоматов, которое позволяет из К1 получить К2. Изоморфизм автоматов К1 и К2 — взаимно однозначный гомоморфизм.
Если существует взаимно однозначное переименование алфавитов К1 и К2, т.е. из К1 можно получить К2 и из К2 можно получить описание К1. Замечание: При изоморфизме происходит только лишь переименование элементов множеств, а при гомоморфизме, помимо переименования, происходит ещё и совмещение (склеивание) некоторых состояний.
Неотличимое состояние — такое состояние автоматов К1 и К2 , имеющих одинаковый входной и выходной алфавит, если для любой входной строки ? К1| qi(1), ?|=K2|qi(2), ?|. Если К1 = К2, то это неотличимые состояния одного и того же автомата. Каждое состояние неотличимо от самого себя.
Неотличимые автоматы — такие К1 и К2 , для которых для любого состояния qi(1) автомата К1 найдется qj(2) ?Q2 , причем q1(1) неотличимо от qj(2).