Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Распоз-ль это специальный алгоритм позволяющий определить принадлежность цепочки символов некоторому языку.
Распознаватель явл-ся частью компелятора и представляети собой часть ПО компелятора.
Фактически работа распознавателей в составе компеляторов сводится к построению дерева вывода входной цепочки, а затем это дерево используется компелятором для построения результирующего кода.
Распознаватель устанавливает факт присутствия ошибки и определяет тип ошибки.
Распознаватели:
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) Всякая целочисл вычислимая по Тьюрингу ф-я рекурсивна.
Универсальная машина Тьюринга:
Дата публикования: 2015-02-03; Прочитано: 478 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!