Детерминированные конечные автоматы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Детерминированный конечный автомат)
м (Обозначения)
Строка 30: Строка 30:
  
 
1.Переход за 1 шаг:
 
1.Переход за 1 шаг:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
+
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если:
 
** <tex>\alpha = c\beta</tex>
 
** <tex>\alpha = c\beta</tex>
 
** <tex>\delta (q, c)=p </tex>
 
** <tex>\delta (q, c)=p </tex>
 
2.Переход за 0 или более шагов:
 
2.Переход за 0 или более шагов:
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
+
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если <tex>\exists n</tex>:
 
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>
 
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>
  
Строка 58: Строка 58:
 
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
 
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
 
}}
 
}}
 
  
 
== Способ хранения автомата ==
 
== Способ хранения автомата ==

Версия 03:57, 13 октября 2010

Детерминированный конечный автомат

Определение:
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов [math]\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math], где [math]\Sigma[/math] -- алфавит, [math]Q[/math] -- множество состояний автомата, [math]s[/math] -- начальное состояние автомата, [math]T[/math] -- Множество допускающих состояний автомата, [math]\delta[/math] -- функция переходов.


Пример :

DKA 1.jpg

q - начальное состояние. r - допускающее состояние.

Процесс допуска

Процесс допуска слова автоматом выглядит так:

  • Изначально автомат находится в стартовом состоянии
  • Ему на вход подается строка
  • Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным
  • Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Обозначения

Определение:
Мгновенное описание (конфигурация) - , где q – текущее состояние, α – оставшиеся символы.</td></tr>

</table>


Для удобства можно ввести следующие обозначения:

1.Переход за 1 шаг:

  • [math]\langle q, \alpha \rangle \vdash \langle p, \beta \rangle[/math], если:
    • [math]\alpha = c\beta[/math]
    • [math]\delta (q, c)=p [/math]

2.Переход за 0 или более шагов:

  • [math]\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle[/math], если [math]\exists n[/math]:
    • [math]\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle[/math]

Автоматные языки

Определение:
[math]L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}[/math] --- язык автомата [math]\mathcal{A}[/math].


Пример:

Автомат, допускающий слова над алфавитом из символов a и b, допускающий слова в которых перед каждым символом b идёт символ a.

(a|ab)*

DKA 2.jpg


Лемма:
[math]\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle[/math]
Доказательство:
[math]\triangleright[/math]
[math]\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.[/math]
[math]\triangleleft[/math]

Способ хранения автомата

Save DKA.jpg

В ячейке таблицы (i, c) храним номер состояния, в которое можно перейти из состояния i по символу c. В массиве Access отмечены допускающие состояния. Таким образом требуется O(|Q||Σ|) памяти.