разработка. Тема 10. 1 Элементы теории автоматов
 Скачать 78.64 Kb.
|
Тема 10.1 Элементы теории автоматовСтудент должен: знать: базовые множества и принцип работы автомата, диаграмму автомата; словарную и финальную функции автомата; уметь: по таблице автомата строить его диаграмму, по диаграмме автомата записывать его таблицу; для заданного автомата по заданному входному слову записывать соответствующее выходное слово. Мы постоянно сталкиваемся с разного рода автоматами, такими, как калькуляторы, телефонные коммутаторы, переключательные схемы лифтов. Все они имеют некие общие черты. А именно, автомат представляет собой устройство, которое может находиться в разных состояниях; эти состояния могут переходить в другие состояния под влиянием внешнего воздействия (называемых входами), например, электронных или механических импульсов. Часто автомат “реагирует”, продуцируя выходы, в качестве которых могут фигурировать, например, результаты вычислений или мелкие монеты. Автоматом называется набор V = (A, Q, B, , ), где A, Q, B – конечные множества, – функция, определенная на множестве QA и принимающая значения из Q:  ; – функция определенная на множестве QА и принимающая значения из В:  . Множество А называется входным алфавитом. Множество Q называется алфавитом состояний. Множество В называется выходным алфавитом. Функция называется функцией переходов. Функция называется функцией выходов. Входными словами автомата V называется произвольная конечная последовательность символов алфавита А. Выходными словами автомата V называется конечная последовательность символов алфавитов В. Способы задания автоматов. 1 способ. Конечные множества A,B,Qможно задавать непосредственным перечислением их элементов. Функция и можно задавать при помощи прямоугольных таблиц. Каждая строка таблиц взаимно однозначно сопоставляется символу  алфавита Q, Q= { ,..., }. Каждый столбец таблиц взаимно однозначно сопоставляется символу  алфавита А, А = { ,..., }. На пересечении строки, соответствующей символу , и столбца, соответствующего символу , содержится символ  ( ).2 способ. Автоматы можно задавать с помощью диаграмм Мура1, которые строятся следующим образом: 1) На плоскости размещается п кругов. Внутри i-го круга записывается символ алфавита Q= { ,..., }.2) Рассматриваются всевозможные пары  , где принадлежит Q, принадлежит А, А = { ,..., }.Для каждой такой пары от круга, в котором записан символ , проводится стрелка к кругу, в котором записан символ . Этой стрелке приписывается пара  . Из каждого круга диаграммы выходит ровно т стрелок (т – количество символов алфавита А). “Супружеский автомат”Рассмотрим следующую ситуацию, относящуюся к несколько идеализированному браку: муж сердит, скучает или счастлив; жена спокойна, кричит или готовит его любимое блюдо. Молчание с её стороны не меняет настроения мужа; крик снижает уровень настроения на одну ступень (конечно, если муж уже сердит, то таким и останется), приготовление любимого блюда делает мужа счастливым. Муж кричит только тогда, когда он сердит, причём его жена кричит. В противном случае он спокоен (выходы). Опишем эту весьма ограниченную модель супружеских отношений в терминах автомата q1 “муж сердит” а1 “жена спокойна” q2 “муж скучает” а2 “жена кричит” q3 “муж счастлив” а3 “жена готовит” b1 “муж кричит” b2 “муж спокоен”
Пример 1.
Рассмотрим принцип работы данного автомата. Пусть дано входное слово: α = 0110100. Найти выходное слово β.
Получаем выходное слово β = 0111110. 1 Мур Элиаким Гастингс (1862-1932) американский математик. Один из основоположников современной математики в США. Основные труды по геометрии, теории групп, теории функций, функциональному анализу и другим разделам математики. |
= 1.
= 
= 
= 
