Эквивалентные автоматы

9.

10.

11. Автомат — последовательность из пяти элементов (Q,Σ,δ,S0,F), где:

Q — множество состояний автомата

Σ — алфавит языка, который понимает автомат

δ — функция перехода, такая что

S0 — начальное состояние

F — множество состояний, называемых «принимающие состояния».

Эквивалентные автоматы

Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными.

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

Минимальная форма автомата S (обозначается как Š) в теории автоматов представляет собой автомат с ň состояниями, образующими множество {σ1..σň}. Минимальный автомат из S строится следующим образом. Характеристические функции автоматов S и Š обозначаются соответственно gs, gz и g's, g'z соответственно. Тогда, если

, то

Таким образом, при построении Š по данному условию не возникает никакой неопределенности.

Алгоритм нахождения минимального автомата был предложен Ауфенкампом и Хоном. Ими было показано, что для нахождения минимального автомата необходимо находить последовательные разбиения Pi автомата S на классы 1, 2, …, k, (k+1) - эквивалентных между собой состояний, до тех пор пока на каком-то (k+1) шаге не окажется, что Pk = Pk+1. Таким образом, разбиение Pk дает все классы эквивалентности состояний автомата S. Всем состояниям S, принадлежащим классу эквивалентности Σl можно приписать общее обозначение, например, σl. Таким образом, автомат Š получается из автомата S путем «объединения» одинаково обозначенных состояний в одно состояние. Способы, которыми это объединение производится, существенно зависят от того, каким образом определен автомат — таблицей, графом или матрицей.

13. Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

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

??? Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.

??? Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Дата добавления: 2015-10-13