а) Написать таблицу состояний данного автомата. б) Считая автомат неициальным, построить эквивалентный автомат Мура. Проверить работу данного автомата и построенного автоматов над одним и тем же словом.
а) Написать таблицу состояний данного автомата. б) Считая автомат неициальным, построить эквивалентный автомат Мура. Проверить работу данного автомата и построенного автоматов над одним и тем же словом.
Задача 49798 а) Написать таблицу состояний данного.
а) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат
Мура. Проверить работу данного и построенного автоматов над одним и тем
же словом.
математика ВУЗ 1136
О решение.
На нашем сайте такое бывает редко, но решение к данной задаче еще никто не написал.
Что Вы можете сделать?
- Выставите данный вопрос вновь. Перейдите на главную страницу.
- Найдите похожую задачу. Используйте поиск.
Решение
Построим сам граф. Столбцы – вершины графа, строки – его рёбра. Если ребро инцидентно вершине, то клетка будет закрашена. Получим:
Составим остовное дерево для данного графа. Остовное дерево графа – это подграф графа, состоящий из всех вершин графа и минимального числа рёбер так, чтобы из любой вершины можно добраться в любую. Сначал включаем в оствное дерево ребро 
Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также включаем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
добавляет к остовному дереву вершину 
, его также оставляем. Ребро 
не добавляет к остовному дереву новых вершин, поэтому его в остовное дерево не включаем. Ребро 
добавляет к остовному дереву вершину 
, поэтому его также включаем. В остовное дерево включены все вершины графа, поэтому остовное дерево построено.
4. А) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.
Изобразим таблицу данного автомата
Локальные автоматы
Пусть [math]G[/math] — граф Майхилла над алфавитом [math]\Sigma[/math] .
Символ [math]c \in \Sigma[/math] назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.
Не пустая строка [math]c_1c_2 \ldots c_n[/math] из [math]\Sigma^*[/math] длиной не менее двух символов, называется разрешенной, если символом [math]c_1[/math] отмечена стартовая вершина, а символом [math]c_n[/math] — конечная, и для всех [math]1 \leqslant i \leqslant n — 1[/math] в [math]G[/math] существует ребро [math](c_i, c_)[/math] .
Язык [math]L(G)[/math] , распознаваемый графом Майхилла, состоит из всех разрешенных строк из [math]\Sigma^+[/math] .
Покажем, что графы Майхилла могут быть представлены в виде автоматов. Пусть [math]\mathcal = (S, \Sigma, i, \delta, T)[/math] — ДКА.
| Определение: |
| Автомат [math]\mathcal[/math] называется локальным (англ. local automaton, Glushkov automaton), если для любого [math]c[/math] из [math]\Sigma[/math] множество [math]\<\delta(s, c) \mid s \in S\>[/math] содержит не более одного элемента. |
| Определение: |
| Локальный автомат [math]\mathcal[/math] называется стандартным локальным автоматом (англ. standard local automation), если в нем нет перехода в начальное состояние. |
Таким образом, автомат является локальным, если для каждого [math]c[/math] из [math]\Sigma[/math] нет переходов, отмеченных [math]c[/math] , или если все они ведут в одно состояние.
Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.
Пусть [math]G[/math] — граф Майхилла. Построим автомат [math]\mathcal[/math] следующим образом:
- Добавим вершину [math]i[/math] в [math]G[/math] с ребрами от [math]i[/math] к каждой стартовой вершине [math]G[/math] ; отметим вершину [math]i[/math] как стартовое состояние.
- Отметим конечные вершины как терминальные состояния.
- Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
Переходы преобразуются следующим образом: По построению стартовое состояние не является терминальным. Покажем, что полученный автомат конечен. Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате. Если мы рассмотрим любое другое состояние [math] s [/math] , то два перехода из [math] s [/math] могут иметь одинаковые метки только в том случае, если в [math]G[/math] оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойству 1. То есть [math]\mathcal[/math] — ДКА. По построению он является стандартным локальным автоматом. Теперь просто проверить, что [math]L(\mathcal) = L(G) [/math] .
[math] \Leftarrow [/math]
- Отметим все состояния [math] \mathcal [/math] , кроме стартового, [math] input [/math] символами, стоящими на ребрах, входящих в эти состояния.
- Сотрем все метки на ребрах [math] \mathcal [/math] .
- Отметим все состояния [math] s [/math] как начальные вершины, если существует переход из [math] i [/math] в [math] s [/math]
- Отметим все терминальные состояния как конечные вершины.
- Удалим вершину [math] i [/math] и все ребра, исходящие из нее.
Пример
Граф Майхилла, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом [math]\Sigma = \[/math] . По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на [math]a[/math] .
Недетерминированный автомат на рисунке 2 является локальным автоматом и распознает тот же самый язык.
Локальный язык
Рассмотрим язык, распознаваемый стандартным локальным автоматом.
| Определение: |
| Язык [math]L \subseteq A^*[/math] называется локальным языком (англ. local language), если [math]L \setminus \varepsilon[/math] может быть описан следующим образом: [math]\exists P, S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*[/math] . |
Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из [math]P[/math] , оканчивается на символ из [math]S[/math] и не содержит пары символов из множества [math]N[/math] .
Пусть [math]L = (P A^* \cap A^* S) \setminus A^* N A^*[/math] — локальный язык. Определим автомат [math]\mathcal[/math] следующим образом:
- набор состояний [math]Q = A \cup \< \varepsilon \>[/math] ,
- начальное состояние [math]\varepsilon[/math] ,
- терминальные состояния [math]S[/math] ,
- [math]\delta(\varepsilon, a) = a[/math] если [math]a \in P[/math] и [math]\delta(a, b) = b[/math] если [math]ab \not\in N[/math] .
Если [math]L[/math] содержит пустую строку, то множество терминальных состояний [math]\mathcal[/math] — [math]S \cup \< \varepsilon \>[/math] .
Автомат является локальным поскольку для каждого состояния [math]s[/math] и любого символа [math]a[/math] [math]\delta(s, a)[/math] либо неопределена либо равна [math]a[/math] . По построению автомат является стандартным. Покажем, что [math]L(\mathcal) = L[/math] .
Пусть [math]x = a_1 \ldots a_n \in L(\mathcal)[/math] . Тогда в автомате существует путь:
[math]\varepsilon \xrightarrow a_1 \xrightarrow a_2 \ldots a_ \xrightarrow a_n[/math] .
Здесь [math]a_n[/math] — терминальное состояние, [math]a_n \in S[/math] . Переход из [math]\varepsilon[/math] в [math]a_1[/math] определен, поэтому [math]a_1 \in P[/math] . Для каждого [math]j: 1 \leqslant j \leqslant n — 1[/math] факт, что переход [math]a_j \rightarrow a_[/math] существует, означает что [math]a_j a_ \not \in N[/math] . Следовательно, [math]x \in L[/math] .
Пусть [math]x = a_1 \ldots a_n \in L[/math] . Тогда [math]a_1 \in P[/math] , [math]a_n \in S[/math] и для каждого [math]j[/math] [math]a_j a_ \not \in N[/math] . Следовательно в автомате существует путь из начального состояния в терминальное:
Язык, распознаваемый локальным автоматом, является локальным.
Алгоритм Глушкова
Описание
Дано регулярное выражение [math]e[/math] . Алгоритм Глушкова строит недетерминированный автомат, который распознает язык [math]L(e)[/math] , распознаваемый [math]e[/math] . Построение происходит в несколько шагов:
- Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть [math]A[/math] — исходный алфавит, [math]B[/math] — новый алфавит.
- Вычисление множеств [math]P(e’), S(e’), N(e’)[/math] , где [math]e'[/math] — линеаризованное регулярное выражение. [math]P(e’)[/math] — множество символов, с которых начинается слово из [math]L(e’)[/math] . [math]S(e’)[/math] — множество символов, на которые оканчивается слово из [math]L(e’)[/math] и [math]N(e’)[/math] — множество пар символов, которые встречаются в слове из [math]L(e’)[/math] . Более формально:
[math]P(e’)=\
[math]S(e’)=\
[math]N(e’)=\
- Вычисление множества [math]\Lambda(e’)[/math] такого что [math]\Lambda(e’)=\\cap L(e’)[/math] .
- Вычисление локального языка с заданными множествами и построение по нему автомата.
- Делинеаризация, переименование каждого символа из [math]B[/math] в соответствующий ему символ из [math]A[/math] .
Пример работы
Автомат, построенный в ходе работы алгоритма Глушкова
Рассмотрим регулярное выражение [math]e = (a(ab)^*)^* + (ba)^*[/math] :
- Линеаризуем его путем добавления индекса к каждому символу:
- Составим множества [math]P[/math] , [math]S[/math] , и [math]N[/math] :
Так как пустое слово принадлежит языку, то [math]\Lambda(e’)=\[/math] .
- Автомат локального языка [math]L’=P’B^*\cap B^*S’\setminus B^*(B^2\setminus N’)B^*[/math] содержит начальное состояние, обозначенное как [math]1[/math] , и состояния для каждого из пяти символов алфавита [math]B=\[/math] .
В построенном автомате существует переход из [math]1[/math] (соответствующего пустой строке) в два состояния из [math]P'[/math] , переход из [math]a[/math] в [math]b[/math] если [math]ab \in N'[/math] , три состояния [math]S'[/math] терминальные (как и состояние [math]1[/math] ).
- Получим автомат для [math]L(e)[/math] , удалив индексы, добавленные на первом этапе.
См. также
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений
- Mark V. Lawson — Finite Automata
- Wikipedia — Glushkov’s construction algorithm
- Теория формальных языков
- Автоматы и регулярные языки
- Другие автоматы