Лекция: Абстрактные распознаватели. Конечные автоматы.

Распоз-ль это специальный алгоритм позволяющий определить принадлежность цепочки символов некоторому языку.

Распознаватель явл-ся частью компелятора и представляети собой часть ПО компелятора.

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

Распознаватель устанавливает факт присутствия ошибки и определяет тип ошибки.

Распознаватели:

1)Машина Тьюринга

2)Автоматы с магазинной памятью(конечный автомат снабженный дополнительным стеком)

3)Линейно-ограниченые автоматы(это машина Тьюринга объем которой определяется длиной последовательности входных символов)

4)Конечные автоматы(наз-ся пятерка следующего вида М(V,Q,q0,F,δ)–автомат: V–алфавит автомата; Q–конечное множество состояний автомата; q0–начальное состояние автомата; F–непустое множество конечных состояний автомата; δ–ф-я переходов к-я отображает декартово произведение множеств VxQ во множество Q)

Конечный автомат наз-ся полностью определенным если для любого а и для любого q существует δ(а,q)=R≤Q

Конечный автомат наз-ся детерминированным если в каждом из его состояний для любого входного символа ф-я перехода содержит не более одного состояния

Преобр-е к детерминированному виду:

1)Q/это множество всех подмножеств в множествеQ

2)q/0=[q0]

3)F/–множество всех таких подмножеств множества Q к-е содержат хотя бы одно из конечных состояний из множ F

4) δ/(a,q/)=r/ принадлежит Q/, где r/–объединение всех множеств R= δ(а,q)

5)Удалить из Q/ все недостижимые состояния. Состояние недостижимо если не при какой входной цепочке невозможен переход автоматом из начального состояния в q

6)Посмотрев правые части равенств в предыдущем пункте добавим начальные состояния и тогда получим новое множество q0

Минимизация: она заключается в построении эквивалентного конечного автомата с минимально возможным числом состояний. Перед миним. Необходимо автомат привести к детерминированному виду и удалить недостижимые состояния.

Минимизация конечного автомата состоит в последовательном разбиении множ. Q на классы эквивалентности до тех пор пока не получится разбиение, к-е уже нельзя измельчить.Классы эквивалентности состояний исходного конечного автомата становятся состояниями результирующего минимизированного конечного автомата.

Столбцы-внут сост, строки-внеш алфав. Если машина нах-ся во внут сост qJ а обозрев ячейка аi, то в обоз ячейку записываем символ аi, Затем машина перейдет во внутр сост qJ.

М оказаться, что в табл пустая ячейка, это означ, что при внутреннем состоянии q данный символ встречаться не м. М оказаться, что аi=аl, т е в ту же ячейку записыв новое значение. М оказ, что qi=qР значит головка осталась в прежнем состоянии.

Начальным внутренним состоянием считают q0. Машина Тьюринга б работать по программе записывать в табл до тех пор, пока в клетке не б записано, что машина не д менять символ в обозреваемой ячейке, не д никуда двигаться. Если такой точки остановки в прогр нет, то машина б работать бесконечно и машина к данному слову не применима. Точка остановки выглядит- aiqJ→ ai$qJ

Применимость к слову м доказать, прослеживая работу программы, не принадлежность м доказать формально. Богатство возможностей и конструкций проявл в том, что если какие-то алг А и В реализ машиной Тьюринга, то м составить разл композицию этих алгоритмов в виде соответств машин Тьюринга.

Пр композиции: 1).Следования: алг А затем алг В 2).Ветвление: Выполн алг А, если в результате работы получили Да, тот выполн алг В 3).Циклы: выполн поочеред алг А и В, пока в рез работы В не даст конкретный рез.

Возможность построения таких композиций доказыв в общ виде независ знач А и В. Рассмотрим 1 вид композиции: пусть имеется 2 алг, реализ для маш Тьюринга А и В. Состояния маш А {q0,…qm}, маш В {q0…qn}. Для реализации композиции н выполнить след действия: перенумеровать машину внутр сост маш В {qm+1…qm+n}, затем в табл справа от Маш А вставить программу маш В, затем все т останова машины А преобраз в команды перехода к состоянию qm+1. Пример компазиции: А – подсчитывает штрихи на ленте, а В – увеличивает десят число на 1.

Описывая разл алг для машины Тьюринга и доказывая реализуемость композ этих машин

Тьюринг выдвин гипотезу, чтот любой алг м б реализован соответствующей машиной – основная гипотеза теории алг в форме Тьюринга. Строго наш тезис доказ нельзя т к понятие всякого алг формально. Его м обосновать представляя разл алгор в виде маш Тьюринга.Дополнительное доказательство маш тезиса м б осуществлено путем доказ эквивалент его др универсал алгор моделями. Эквивалентность алгоритмич мод маш Тьюринга м доказ строго, в теории алг доказ 2 теоремы:1) Фя f назыв вычислимой по Тьюрингу, если сущ такая маш Тьюринга, что для всех исходных слов из обл определ ф-ии рез-т работы маш совпад со значен фии f на этом слове.(не завершит если не из области определ. 2) Всякая целочисл вычислимая по Тьюрингу ф-я рекурсивна.

Универсальная машина Тьюринга: