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

Материал из Викиконспекты
Перейти к: навигация, поиск
(дописано куча всего)
Строка 8: Строка 8:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Мгновенная кофигурация''' {{---}}}}
+
'''Мгновенная кофигурация''' {{---}} это пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>}}
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если:
+
 
** <tex>\alpha = c\beta</tex>
+
Определим некоторые операции для мгновенных конфигураций.
** <tex>p \in \delta (q, c)</tex>
+
{{Определение
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если <tex>\exists n</tex>:
+
|definition =
** <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 p, \beta \rangle</tex> '''выводится за один шаг''' из <tex>\langle q, \alpha \rangle </tex>, если:
 +
* <tex>\alpha = c\beta</tex>
 +
* <tex>p \in \delta (q, c)</tex>.
 +
Это также записывают так: <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' из <tex>\langle q, \alpha \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, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
НКА '''допускает''' слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
 +
}}
 +
 
 +
Менее формально это можно описать так: НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.
  
Автомат допускает слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
 
Процесс допуска происходит так же, как в ДКА, в котором Мерлин помогает выбрать правильный переход.
 
  
 
== Язык автомата ==
 
== Язык автомата ==
 +
{{Определение
 +
|definition =
 +
Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>.
 +
* <tex> \mathcal{L}(\mathcal{A}) =  \lbrace w | \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace </tex>
 +
}}
  
 +
Язык НКА тоже является автоматным языком, так как можно [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|построить из НКА эквивалентный ДКА]], поэтому вычислительная мощность этих двух автоматов совпадает.
  
 
== Пример ==
 
== Пример ==
Строка 28: Строка 50:
 
[[Файл:NKA_1.jpg]]
 
[[Файл:NKA_1.jpg]]
  
== Способ хранения ==
+
== Алгоритм определяющий допустимость автоматом слова ==
 +
 
 +
По сравнению с ДКА, определять допускает ли НКА слово сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя.
 +
Поступим по-другому, определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex>.
 +
* <tex> R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </tex>
  
== Алгоритм определяющий допустимость автоматом слова ==
+
Пусть нам нужно определить допускает ли НКА слово <tex> w </tex>. Заметим, что если <tex> \exists t \in T : t \in R(w) </tex>, то слово допускается, так как <tex> \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle </tex> по определению <tex> R(w) </tex>. Алгоритм состоит в том, чтобы построить <tex> R(w) </tex>.
 +
 
 +
Очевидно, что <tex> R(\varepsilon) = \lbrace s \rbrace </tex>. Пусть мы построили <tex> R(\alpha) </tex>, как же получить <tex> R(\alpha c)</tex>, где <tex> c \in \Sigma </tex>. Заметим, что
 +
* <tex> R(\alpha c) = \lbrace q | q \in \delta(p, c), p \in R(\alpha) \rbrace </tex>,
 +
так как
 +
* <tex> \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle p, c \rangle \vdash \langle q, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle q, \varepsilon \rangle </tex>, где <tex> q \in \delta(p, c) </tex>
 +
 
 +
Теперь, когда мы научились добавлять символ к строке, возьмем <tex> R(\varepsilon) </tex>, будем добавлять <tex> w_1, w_2 \ldots w_{|w|} </tex> и находить для каждого <tex> R(w_1\ldots w_k) </tex>.
 +
 
 +
Когда мы получим <tex> R(w) </tex>, проверим что в нем есть терминальное состояние.
  
 +
Псевдокод:
 +
<font size = 3>
 +
    <tex> R_0 = \lbrace s \rbrace </tex>
 +
    for i = 1 to length(w) do
 +
        <tex> R_i = \varnothing </tex>
 +
        for <tex> p \in R_{i - 1} </tex> do
 +
            <tex> R_i = R_i \cup \delta(p, w_i) </tex>
 +
    accepts = False
 +
    for <tex> t \in T </tex> do
 +
        if (<tex> t \in R_{|w|} </tex>) then
 +
            accepts = True
 +
</font>
 
== См. также ==
 
== См. также ==
  
 
* [[Детерминированные конечные автоматы]]
 
* [[Детерминированные конечные автоматы]]

Версия 01:47, 14 ноября 2011

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


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

Определение:
Мгновенная кофигурация — это пара [math] \langle p, q \rangle [/math], [math] p \in Q [/math], [math] q \in \Sigma^*[/math]


Определим некоторые операции для мгновенных конфигураций.

Определение:
Говорят, что [math] \langle p, \beta \rangle[/math] выводится за один шаг из [math]\langle q, \alpha \rangle [/math], если:
  • [math]\alpha = c\beta[/math]
  • [math]p \in \delta (q, c)[/math].
Это также записывают так: [math]\langle q, \alpha \rangle \vdash \langle p, \beta \rangle[/math]


Определение:
Говорят, что [math] \langle p, \beta \rangle[/math] выводится за ноль и более шагов из [math]\langle q, \alpha \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]\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle[/math]


Определение:
НКА допускает слово [math]\alpha[/math], если [math]\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle[/math].


Менее формально это можно описать так: НКА допускает слово [math] \alpha [/math], если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово [math] \alpha [/math].


Язык автомата

Определение:
Множество слов, допускаемых автоматом [math] \mathcal{A} [/math], называется языком НКА [math] \mathcal{A} [/math].
  • [math] \mathcal{L}(\mathcal{A}) = \lbrace w | \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace [/math]


Язык НКА тоже является автоматным языком, так как можно построить из НКА эквивалентный ДКА, поэтому вычислительная мощность этих двух автоматов совпадает.

Пример

Автомат, допускающий слова над алфавитом из символов 0 и 1, допускающий слова оканчивающиеся на 0101.

(0|1)*0101

NKA 1.jpg

Алгоритм определяющий допустимость автоматом слова

По сравнению с ДКА, определять допускает ли НКА слово сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя. Поступим по-другому, определим множество всех достижимых состояний из стартового по слову [math] \alpha [/math].

  • [math] R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace [/math]

Пусть нам нужно определить допускает ли НКА слово [math] w [/math]. Заметим, что если [math] \exists t \in T : t \in R(w) [/math], то слово допускается, так как [math] \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle [/math] по определению [math] R(w) [/math]. Алгоритм состоит в том, чтобы построить [math] R(w) [/math].

Очевидно, что [math] R(\varepsilon) = \lbrace s \rbrace [/math]. Пусть мы построили [math] R(\alpha) [/math], как же получить [math] R(\alpha c)[/math], где [math] c \in \Sigma [/math]. Заметим, что

  • [math] R(\alpha c) = \lbrace q | q \in \delta(p, c), p \in R(\alpha) \rbrace [/math],

так как

  • [math] \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle p, c \rangle \vdash \langle q, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle q, \varepsilon \rangle [/math], где [math] q \in \delta(p, c) [/math]

Теперь, когда мы научились добавлять символ к строке, возьмем [math] R(\varepsilon) [/math], будем добавлять [math] w_1, w_2 \ldots w_{|w|} [/math] и находить для каждого [math] R(w_1\ldots w_k) [/math].

Когда мы получим [math] R(w) [/math], проверим что в нем есть терминальное состояние.

Псевдокод:

   [math] R_0 = \lbrace s \rbrace [/math]
   for i = 1 to length(w) do
       [math] R_i = \varnothing [/math]
       for [math] p \in R_{i - 1} [/math] do
           [math] R_i = R_i \cup \delta(p, w_i) [/math]
   accepts = False
   for [math] t \in T [/math] do
       if ([math] t \in R_{|w|} [/math]) then
           accepts = True

См. также