32.Алгоритмические возможности: что могут и что не могут вычислять автоматы. Примеры.

33.Эквивалентность автоматов. Алгоритм минимизации автоматов.

Автоматов эквивалентность – отношение эквивалентности на множестве автоматов, возникающее в связи с изучением тех или иных содержательных свойств автоматов. Обычно таким свойством является автоматов поведение, так что два автомата считаются эквивалентными, если они имеют одинаковое поведение. При этом в качестве поведения автомата, как правило, рассматривается система функций, реализуемых автоматом (см. Автомат конечный). Для конечных автоматов такое отношение эквивалентности разрешимо, и потому существует алгоритм минимизации автоматов, т. е. построения для заданного автомата эквивалентного ему автомата с минимальным числом состояний (минимального автомата).

Для определения А. э. удобно использовать понятие эквивалентности состояний: состояния s и s’ соответственно автоматов U и U’ (быть может, совпадающих) наз. эквивалентными, если инициальные автоматы  Us и Us’ реализуют одну и ту же функцию. Тогда эквивалентность автоматов U и U’ равносильна тому, что для любого состояния автомата U найдется эквивалентное ему состояние автомата U’, и обратно. Автомат является минимальным тогда и только тогда, когда любые два его состояния неэквивалентны. Для любого автомата минимальный автомат определяется однозначно с точностью до изоморфизма. Алгоритм разрешения этого отношения эквивалентности для конечных автоматов основывается на теореме Мура о том, что состояния s и s’ автомата U эквивалентны точно тогда, когда функции, реализуемые инициальными автоматами Us и U s’ совпадают на словах длины n-1, где n – число состояний автомата U’. В случае, когда состояния s и s’ принадлежат, соответственно, двум автоматам U и U’ эта оценка равна n+n’-1, где n’ – число состояний автомата U’. На этой же теореме основан известный алгоритм минимизации конечных автоматов, состоящий в построении так наз. приведенного автомата, состояниями которого являются классы эквивалентных состояний, а функции переходов и выходов естественно индуцируются соответствующими функциями исходного автомата. Приведенный автомат является минимальным, поскольку любые два его состояния неэквивалентны.

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

Состояния am и as являются эквивалентными, если λ(am, ξ) = λ(as, ξ)  для всевозможных входных слов ξ.

Алгоритм: 1. Находим последовательные разбиения п1, п2, …, пк, пк+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = пк+1.

2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата  S’ = {A’,z,w,σ’,λ’,a1’} эквивалентному автомату S.

3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.

4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.