Изоморфные и эквивалентные автоматы

ЛЕКЦИЯ 4. 6. ЭКВИВАЛЕНТНЫЕ АВТОМАТЫ 6.1. Изоморфные и эквивалентные автоматы Автоматы изоморфны если их описание одинаково с точностью до переобозначений. Два инициальных автомата будем называть эквивалентными автоматами, если любую одну и ту же входную последовательность они перерабатывают в одну и туже выходную последовательность. Неинициальные автоматы будем называть эквивалентными, если для любого состояния, взятого в качестве начального одного из автоматов, найдется в другом автомате состояние, назначив которое начальным получим эквивалентность переработки информации входной в выходную. 6.2. Минимальные автоматы 6.2.1. Автомат, эквивалентный заданному и имеющий наименьшее возможное число состояний, называется минимальным. Если автоматы всюду определены и эквивалентны, то они имеют изоморфные минимальные автоматы. Для частично-определенных автоматов это положение может не выполняться. Минимизация автомата возможна, если в автомате есть состояния, которые могут быть объединены в одно состояние. Такие состояния называют эквивалентными состояниями. Иначе говоря, автомат минимальный, если у него нет эквивалентных состояний. Состояния p, q одного и того же автомата эквивалентны, если при подаче одной и той же (любой) входной последовательности с начальными состояниями p или q образуются одинаковые выходные последовательности. 6.2.2. Достаточным условием эквивалентности состояний является совпадение соответствующих им строк в автоматной таблице. Такие состояния называют явно эквивалентными. Если строки одинаковы за исключением переходов в себя при одних и тех же входах, то такие состояния так же явно эквивалентны. Поэтому в автоматных таблицах следует переход в себя указывать не именем состояния, а каким-либо одинаковым символом, например таким: $. После такой замены строки могут стать одинаковыми. 6.2.3. Если состояния не явно эквивалентны, то для эквивалентности двух состояний автомата с n состояниями (n>1) достаточно, чтобы совпадали реакции (последовательности выходных значений) этих двух состояний на любые возможные входные последовательности длины, не превышающей n-1. Определим последовательность отношений эквивалентности E0, E1,…,En-1 на множестве состояний Q, которым соответствует разбиение множества Q на классы эквивалентности. В отношении E0 состояния p и q эквивалентны (p≡q)0, если в автомате Мура выходные значения этих состояний одинаковы, в автомате Мили (p≡q)0, если в строках, соответствующих этим состояниям, выходные значения одинаковы для одних тех же входов. В отношении эквивалентности Ei+1 состояния (p≡q)i+1, если (p≡q)i  (g(p,t) ≡ g(q,t))i для ⱯtA. Таким образом при увеличении индекса i класс эквивалентности не может увеличиться, а измельчиться может. 6.2.4. Алгоритм: 1) Явно эквивалентные состояния заменяются одним состоянием. 2) Вычисление E0 тривиально (см. выше). Для вычисления следующих отношений эквивалентности в клетки таблицы записываются имена классов эквивалентности каждого из состояний. 3) Вычисление Ei. Состояния из одного класса эквивалентности в отношении Ei–1, в строках которых одинаковые комбинации имён классов эквивалентности образуют новый класс эквивалентности или остаются в старом. 4) Если количество различных классов эквивалентности не увеличилось или равно числу состояний, то вычисление закончено, иначе пункт (3). 5) За не более чем n-1 итерацию классы эквивалентности вычислены. Каждому классу эквивалентности последнего разбиения сопоставляется одно состояние. Пример 6.2-1. Автомат Мура. A Q 1 2 3 4 5 6 F 1 1 a b c 2 4 4 4 2 3 3 5 6 4 3 2 1 2 3 6 6 5 E0 a b A A A A B B A/2 A/4 A/4 A/4 A/2 A/3 A/3 B/5 B/6 A/4 A/3 A/2 c E1 A/1 A A/2 A1 A/3 A1 B/6 A2 B/6 B B/5 B a b c E2 A A2/4 B/5 A1/2 A1 A2/4 B/5 A1/2 A1 A2 A1/2 A1/3 B/6 B A1/2 A1/3 B/6 B Объединив эквивалентные состояния, получим таблицу автомата Мура. A Q A A1 A2 B F 1 a b c A1 A2 A2 A1 A1 B A2 A1 A A1 B B Пример 6.2-2. Автомат Мили. A Q 1 2 3 4 5 6 7 8 a b c E0 a b 1,2 0,1 0,1 1,5 0,7 1,5 1,3 0,6 0,2 1,3 1,2 0,3 1,8 0,2 0,3 1,8 0,4 1,3 1,2 0,1 1,5 0,7 0,6 1,6 A B B A B A A B B/2 A/1 A/1 B/5 A/7 B/5 B/3 A/6 B/2 B/3 B/2 B/3 B/8 B/2 B/3 B/8 A/4 A B/3 B B/2 B A/3 A B/5 B A/7 A A/6 A A/6 B1 a b a 1 2 3 4 5 6 7 8 b c B2/5 B/3 A/3 B2/5 B/2 A/7 E3 A B B A1 A A1 A B1 c E1 a b c A/7 B1/8 B/5 c E4 A B B A1 A A1 B/3 B/3 A1/6 A2 B1 a b E2 A B B A B2 A A B1 c E5 A B B A1 B2 B2/5 B/2 A1/7 A3 A2 B1 Объединив эквивалентные состояния, получим таблицу автомата Мили. A Q A B A1 B2 A3 A2 B1 a b c 1,B 0,A 1,B2 0,A2 1,B2 1,B 0,A3 0,B 1,B 0,B 1,B1 0,B 0,B 1,B1 0,A1 1,B 0,A 1,B2 0,A2 0,A3 1,A3 7. АВТОМАТЫ РАСПОЗНАВАНИЯ ЯЗЫКОВ 7.1. СЛОВА 7.1.1. Определения. Алфавитом называется конечное непустое множество А={a₁,…,aₙ}. Его элементы aₜ называются символами. 7.1.2. Определение: словом (цепочкой, строкой, кортежем) в алфавите А называется конечная последовательность ãₜ=(aₜ1,…,aₜₘ) элементов А. 7.1.3. Определения. Длина слова ãₜ=(aₜ1,…,aₜₘ) обозначаемая |ãₜ|=m, есть число символов в ãₜ. Слово, не содержащее ни одного символа (т.е. последовательность длины 0), называется пустым словом и обозначается ε. 7.1.4. Определения. Множество всех слов в алфавите А обозначается А*. Множество всех непустых слов в алфавите A обозначается A+. 7.1.5. Определение: если ã и ỹ − слова в алфавите A, то слово ãỹ (результат приписывания слова ỹ в конец слова ã) называется катенацией (конкатенацией, сцеплением) слов ã и ỹ. Если ã − слово и n  ℕ, то через aⁿ обозначается слово, состоящее из n символов а. а⁰ ≝ ε (знак ≝ читается «равно по определению»). Пример: ba3 = baaa, (ba)3 = bababa. 7.1.6. Определение: через |ỹ|a обозначается количество вхождений символа a в слово ỹ. Пример: Если A = {a, b, c}, то |baaa|a = 3, |baaa|b = 1, |baaa|c = 0. 7.1.7. Определения. Слово ã − префикс (начало) слова ỹ (обозначение ã ⊏ ỹ, ã = Pref(ỹ), если ỹ = ãũ. Пример: ε ⊏baa, b ⊏baa, ba ⊏baa, baa ⊏baa. Слово ã − суфикс (конец) слова ỹ (обозначениеỹ ⊐ ã, ã = Suf(ỹ), если ỹ = ũã. Слово ã – подслово слова ỹ, если ỹ = ũãῦ. 7.1.8. Определение: обращением или зеркальным образом слова ã (обозначается ãᴿ) называется слово, составленное из символов слова ã в обратном порядке. Пример: Если ũ = baaca, то ũᴿ = acaab. 7.2. ЯЗЫКИ 7.2.1. Определение: если L ⸦ A*, то L называется языком (формальным языком) над алфавитом A. 7.2.2. Определение: пусть L1, L2 ⸦ A*. Тогда L1L2 ={ũỹ | ũ ∈ L1, ỹ  L2}. Язык L1L2 называется катенацией языков L1 и L2. Пример: Если L1 = {a, abb} и L2 = {bbc, c}, то L1L2 = {ac, abbc, abbbbc}. 7.2.3. Определение: Пусть L ⸦ A*, Тогда Ln = L...Ln раз, L0 = {ε} 7.2.4. Определение: итерацией языка L (обозначение L*) называется язык n nℕL . 7.2.5. Определение: пусть L ⸦ А*. Тогда LR = {ãR | ã  L}. 7.3. Автоматы 7.3.1. Автомат можно рассматривать как устройство, распознающее некоторый язык над входным алфавитом. Напомним, в инициальном автомате D=(A,B,Q,g,f,q0) функция g: QA→Q определяет конечное множество переходов (p,a,q)g из p в q, символ a − метка этого перехода, где p,qQ, aA. Автомату сопоставлен ориентированный размеченный граф, в котором дуга (p,a,q)g соединяет вершину p (начало) с вершиной q (конец), с меткой в виде символа аА. 7.3.2. Определения. Путь конечного автомата − это последовательность (e1,e2,…,en-1), где n ⩾ 0 и ei=(qi−1,аi,qi)g для каждого i. При этом q0 − начало пути, qn − конец пути, n − длина пути, слово ã=a1…an − метка пути. (Любому конечному пути мы приписываем одно слово, читая символы вдоль этого пути.) 7.3.3. Пусть язык Ly представим в инициальном автомате выходным символом yB. В автоматном графе инициального автомата языку Ly соответствуют все те слова, которые переводят автомат из начального состояния q0 к дугам (в автомате Мили) или вершинам (в автомате Мура), помеченным выходным символом y. Слова языка Ly называют также событиями. Путь, меткой которого является слово языка Ly называется успешным. Слово ã допускается конечным автоматом D, если оно является меткой некоторого успешного пути. 7.3.4. Определение: язык, распознаваемый конечным автоматом D, − это язык L(D), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат D распознаёт язык L(D). Если орграф конечного автомата содержит цикл, то количество слов в таком языке бесконечно. 7.3.5. Определение: Язык L называется автоматным, если существует конечный автомат, распознающий этот язык. Каждый конечный язык является автоматным. 7.3.6. Удобно в качестве распознающего автомата рассматривать разновидность автомата Мура − автомат без выхода (A,Q,g,q0,FQ) с некоторым подмножеством состояний F, которые называются представляющими или финальными состояниями. Язык L представим в автомате без выхода, если L состоит из тех и только тех слов, которые переводят автомат из начального состояния в состояния из множества F. Если начальное состояние принадлежит множеству финальных состояний F, то язык будет включать слово нулевой длины − пустое слово ε. Пустое слово не следует путать с пустым (невозможным) событием (т.е. с пустым множеством слов). Автомат представляет пустое событие, если ни одно из его финальных состояний не достижимо из начального состояния. Автомат представляет систему (семейство) непустых языков {Li}, если каждый из языков представлен отдельным (своим) подмножеством финальных состояний {Fi} или различающимися финальными выходными символами − индикаторами {yi}. Пустое слово может принадлежать не более чем одному языку. 7.3.7. Не все языки автоматные. Любое конечное множество слов конечной длины представимо в автомате. В тоже время существуют бесконечные языки, не представимые в автомате. В некоторых случаях по описанию языка это свойство может быть установлено. Например, язык, состоящий из всех слов, в которых число нулей равно числу единиц, не автоматный. Интуитивные соображения состоят в том, что автомат способен “считать” только до числа своих состояний, а поскольку число состояний автомата конечно, то он и не может распознать все слова из этого языка (разница между количеством нулей и единиц может быть неопределённо большой). Но, в общем случае, задача установления представимости языка алгоритмически не разрешима. В силу сказанного следует, что надо, по возможности, пользоваться средствами спецификации, обеспечивающими представимость языка. Перечислим некоторые из таких способов. 7.3.8. Дефинитный (определенный) язык может быть представлен как катенация А*Ω, где А – входной алфавит, Ω – конечное множество слов ограниченной длины. Этот язык является бесконечным языком из слов, заканчивающихся словами ῶΩ. Проектируя автомат, распознающий дефинитный язык, удобно сопоставить состояниям автомата все различные префиксы (начала) распознаваемых слов. При поступлении нового символа автомат переходит в состояние, которое соответствует одному из префиксов, совпадающему с суффиксом нового слова, если таких совпадений более одного, то выбирается самое длинное. Одно из состояний должно соответствовать пустому началу. Будем его обозначать символом . Пример 7.3.-1. Спроектировать автомат, который устанавливает на выходе 1, если последние 4 такта это последовательность 0110. Автомат должен распознать в последовательности символов следующее слово: 0110. Этому слову соответствуют следующие различные префиксы: , 0, 01, 011, 0110. Тогда автомат Мура задается следующей автоматной таблицей: № сост. вых. 1   1 $ 01 2 01 10 011 3 011 0110  4 0110 1 01 А это диаграмма автомата Мура: Распознаём тоже самое событие, но автоматом Мили. № 1 2 3 сост.  01 011 1 0/0 $/0 10/0 0/1 /0 01/0 011/0 /0 Следующий пример несколько сложнее. Пример 7.3.-2. Спроектировать автомат, который устанавливает на выходе 1, если последние 4-е такта это последовательность 0110 или 1001. Автомат должен распознать в последовательности символов следующие слова: 0110, 1001. Этим словам соответствуют следующие различные префиксы: , 0, 1, 01, 10, 011, 100, 0110, 1001. Тогда автомат Мура задается следующей автоматной таблицей: № 1 2 3 4 5 6 7 8 сост.  1 01 10 011 100 0110 1001 вых. 1 1 $ 10 10 100 0110 100 10 1 1 01 $ 011 01 1 1001 01 011 Вариант для автомата Мили. № 1 2 3 4 5 6 сост.  1 01 10 011 100 1 0/0 $/0 10/0 10/0 100/0 0/1 0/0 1/0 01/0 $/0 011/0 01/0 1/0 1/1 7.3.9. Асинхронный язык. В асинхронный язык входят слова, в которых повторение любого из символов может быть произвольным. Точнее, если слово ã принадлежит асинхронному языку, то в языке также содержатся все слова, полученные из ã повторениями любых букв из ã либо вычеркиванием из ã некоторых повторений отдельных букв. Функция переходов автомата, определяющего асинхронный язык, имеет следующую особенность: для любого состояния q выполняется: если q:=g(z,a), то q:=g(q,a). Автомат может перейти в другое состояние только при изменении входного символа. Назовем ядром асинхронного языка язык, в котором нет повторений символов. В частности, если ядро – дефинитный язык, то при синтезе автомата, распознающего асинхронный язык с таким ядром, можно воспользоваться приемом из пункта 7.3.8. – сопоставить состояниям автомата префиксы распознаваемых слов ядра. Пример 7.3.-3. Спроектировать автомат с двухразрядным входом (in1,in2) и одноразрядным выходом, который индицирует следующее событие: после нулей на обеих линиях по каждой из линий in1 и in2 прошло ровно по одному стробу любой длительности, строб на линии in2 не начинался раньше чем строб на линии in1. Обозначим возможные символы (сочетания значений сигналов) на входах автомата следующим образом: in1 in2 1 a 1 b q 1 1 c Имеем дело с асинхронным языком. Если удалить все повторения символов, то получим дефинитный язык со следующими минимальными последовательностями, которые должен распознать автомат: aca abca acba abcqa acqa abqa abcba abaqa Последний вариант (a b a q a) требует уточнения в постановке задачи и может рассматриваться или не рассматриваться. Слегка упростим задачу – пусть не будет этого варианта. Из явной эквивалентности всех финальных состояний следует эквивалентность состояний 6≡12 и 7≡9≡14. № 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Q Λ a ac ab aca acb acq abc abq acba acqa abcb abca abcq abqa abcba abcqa Fl a a $ aca a $ acba acqa abca abqa $ $ abcba $ abcqa $ $ $ 1 1 1 1 1 1 1 b Λ ab acb $ ab $ Λ abcb Λ ab ab $ ab Λ ab ab ab c Λ ac $ abc ac Λ Λ Λ Λ ac ac Λ ac Λ ac ac ac q Λ Λ acq abq Λ Λ $ abcq $ Λ Λ Λ Λ $ Λ Λ Λ эквивалентности 5≡10≡11≡13≡15≡16≡17 6≡12 7≡9≡14 7≡9≡14 5≡10≡11≡13≡15≡16≡17 5≡10≡11≡13≡15≡16≡17 6≡12 5≡10≡11≡13≡15≡16≡17 7≡9≡14 5≡10≡11≡13≡15≡16≡17 5≡10≡11≡13≡15≡16≡17 5≡10≡11≡13≡15≡16≡17 Объединив эквивалентные состояния, получим таблицу автомата Мура. Q 1 2 3 4 5 6 7 F Fl a 2 $ F 2 F F F $ 1 b 1 4 5 $ $ 1 5 4 c 1 3 $ 7 1 1 1 4 q 1 1 6 6 1 $ 6 1 Вариант для автомата Мили. № 1 2 3 4 5 6 7 8 9 10 Q Λ a ac ab acb acq abc abq abcb abcq a a/0 $/0 a/1 a/0 a/1 a/1 a/1 a/1 a/1 a/1 b Λ/0 ab/0 acb/0 $/0 $/0 Λ/0 abcb/0 Λ/0 $/0 Λ/0 c Λ/0 ac/0 $/0 abc/0 Λ/0 Λ/0 Λ/0 Λ/0 Λ/0 Λ/0 q Λ/0 Λ/0 acq/0 abq/0 Λ/0 $/0 abcq/0 $/0 Λ/0 $/0 эквивалентности 5≡9 6≡8≡10 6≡8≡10 5≡9 6≡8≡10 Q 1 2 3 4 5 6 7 a 2/0 $/0 2/1 2/0 2/1 2/1 2/1 b 1/0 4/0 5/0 $/0 $/0 1/0 5/0 c 1/0 3/0 $/0 7/0 1/0 1/0 1/0 q 1/0 1/0 6/0 6/0 1/0 $/0 6/0