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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 11 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Недетерминированный конечный автомат''' (НКА) {{---}} пятерка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>, где <tex>\Sigma</tex> {{---}} алфавит, <tex>Q</tex> {{---}} множество состояний автомата, <tex>s</tex> {{---}} начальное состояние автомата, <tex>T</tex> {{---}} множество допускающих состояний автомата, <tex>\delta</tex> {{---}} функция переходов.
+
'''Недетерминированный конечный автомат (НКА)''' (англ. ''Nondeterministic finite automaton, NFA'') {{---}} пятёрка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>, где <tex>\Sigma</tex> {{---}} алфавит, <tex>Q</tex> {{---}} множество состояний автомата, <tex>s</tex> {{---}} начальное состояние автомата, <tex>T</tex> {{---}} множество допускающих состояний автомата, <tex>\delta</tex> {{---}} функция переходов.
Таким образом, единственное отличие НКА от ДКА {{---}} существование нескольких переходов по одному символу из одного состояния.
+
Таким образом, единственное отличие НКА от [[Детерминированные_конечные_автоматы | ДКА]] {{---}} существование нескольких переходов по одному символу из одного состояния.
 
}}
 
}}
  
 
== Процесс допуска ==
 
== Процесс допуска ==
 +
 +
НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.
 +
Теперь это опишем более формально.
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Мгновенная кофигурация''' {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.
+
'''Мгновенное описание''' (англ. ''snapshot'') {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.
 
}}
 
}}
 
+
Определим некоторые операции для мгновенных описаний.
Определим некоторые операции для мгновенных конфигураций.
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за один шаг''' из <tex>\langle q, \alpha \rangle </tex>, если:
+
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за один шаг''' (англ. ''directly yields'') из <tex>\langle q, \alpha \rangle </tex>, если:
 
* <tex>\alpha = c\beta</tex>;
 
* <tex>\alpha = c\beta</tex>;
 
* <tex>p \in \delta (q, c)</tex>.
 
* <tex>p \in \delta (q, c)</tex>.
 
Это также записывают так: <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>.
 
Это также записывают так: <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>.
 
}}
 
}}
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</tex>:
+
[[Транзитивное замыкание#Рефлексивно-транзитивное замыкание | Рефлексивно-транзитивное замыкание]] отношения <tex> \vdash </tex> обозначается как <tex> \vdash^*</tex>. <br>
* <tex>\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \vdash \langle u_{n-1}, c_n \beta\rangle \vdash \langle p, \beta \rangle</tex>
+
И говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.
Это также записывают так: <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.
+
<!--Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</tex>:
 +
* <tex>\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \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 =
 
|definition =
НКА '''допускает''' слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
+
НКА '''допускает''' (англ. ''accepts'') слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
 
}}
 
}}
 
Менее формально это можно описать так: НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.
 
 
  
 
== Язык автомата ==
 
== Язык автомата ==
Строка 39: Строка 38:
 
|definition =  
 
|definition =  
 
Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>.  
 
Множество слов, допускаемых автоматом <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>.
+
* <tex>L(\mathcal{A}) =  \lbrace w \ | \ \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace </tex>.
 +
В этом случае также говорят, что автомат <tex> \mathcal{A} </tex> '''распознаёт''' (англ. ''recognize'') язык <tex> L </tex>.
 
}}
 
}}
  
Язык НКА тоже является автоматным языком, так как можно [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|построить из НКА эквивалентный ДКА]], поэтому вычислительная мощность этих двух автоматов совпадает.
+
Язык НКА является автоматным языком, так как для любого НКА можно [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|построить эквивалентный ему ДКА]], а значит, вычислительная мощность этих двух автоматов совпадает.
  
 
== Пример ==
 
== Пример ==
[[Файл:NFA.png|600px]]
+
[[Файл:Finite state machine 4.png|600px]]
  
 
Это НКА, который распознает язык из алфавита <tex> \lbrace 0, 1 \rbrace </tex>, где на четвертой с конца позиции стоит 0.
 
Это НКА, который распознает язык из алфавита <tex> \lbrace 0, 1 \rbrace </tex>, где на четвертой с конца позиции стоит 0.
  
 
== Алгоритм, определяющий допустимость автоматом слова ==
 
== Алгоритм, определяющий допустимость автоматом слова ==
Этот алгоритм решает следующую задачу: заданы НКА и слово, нужно определить, допускает ли НКА данное слово.
+
===Постановка задачи===
 +
Пусть заданы НКА и слово <tex>w</tex>. Требуется определить, допускает ли НКА данное слово.
 +
 
 +
===Алгоритм===
 +
Определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex> : <tex> R(\alpha) = \lbrace p \ | \ \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </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> \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> R(\varepsilon) = \lbrace s \rbrace </tex>. Пусть мы построили <tex> R(\alpha) </tex>, как же получить <tex> R(\alpha c)</tex>, где <tex> c \in \Sigma </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> \forall q \in \delta(p, c) </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> \forall 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(\alpha) </tex> строить <tex> R(\alpha c)</tex>, возьмем <tex> R(\varepsilon) </tex> и будем последовательно вычислять <tex>R(w[1 \ldots k])</tex> для <tex> k=1 \ldots |w| </tex>.
  
Когда мы получим <tex> R(w) </tex>, проверим, есть ли в нем терминальное состояние.
+
Таким образом, мы получим <tex>R(w)</tex>, и всё, что осталось — проверить, есть ли в нём терминальное состояние.
  
Псевдокод:
+
===Псевдокод===
<font size = 3>
+
'''bool''' accepts(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex>: '''Automaton''', <tex>\mathtt{w}</tex>: '''String'''):
    <tex> R_0 = \lbrace s \rbrace </tex>
+
  <tex> R_0 = \lbrace s \rbrace </tex>
    for i = 1 to length(w) do
+
  '''for''' i = 1 '''to''' <tex>\mathtt{w}</tex>.length
        <tex> R_i = \varnothing </tex>
+
      <tex> R_i = \varnothing </tex>
        for <tex> p \in R_{i - 1} </tex> do
+
      '''for''' (<tex> q </tex> '''in''' <tex> R_{i - 1} </tex>)
            <tex> R_i = R_i \cup \delta(p, w[i]) </tex>
+
          <tex> R_i = R_i \cup \delta(q, \mathtt{w}[i]) </tex>
    accepts = False
+
  '''return''' <tex> R_{|\mathtt{w}|} \cap T \neq \varnothing </tex>
    for <tex> t \in T </tex> do
 
        if <tex> t \in R_{|w|} </tex> then
 
            accepts = True
 
</font>
 
  
 
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
 
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
 +
 
== См. также ==
 
== См. также ==
  
 
* [[Детерминированные конечные автоматы]]
 
* [[Детерминированные конечные автоматы]]
 
* [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
 
* [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
== Литература ==
+
== Источники информации ==
* ''Ю. Громкович'' — '''Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию''' : Пер. с нем. — издательство БХВ-Петербург, 2010. — 336 с. : ISBN 978-5-9775-0406-5
+
* ''Ю. Громкович'' Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 2010. — С. 87. ISBN 978-5-9775-0406-5
 +
* ''John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman'' Introduction to Automata Theory, Languages, and Computation. Second edition. P. 71. ISBN 0-201-02988-X
 +
* [[wikipedia:en:Nondeterministic finite automaton | Wikipedia {{---}} Nondeterministic finite automaton]]
 +
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:17, 4 сентября 2022

Определение:
Недетерминированный конечный автомат (НКА) (англ. Nondeterministic finite automaton, NFA) — пятёрка [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] \alpha [/math], если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово [math] \alpha [/math]. Теперь это опишем более формально.

Определение:
Мгновенное описание (англ. snapshot) — пара [math] \langle p, q \rangle [/math], [math] p \in Q [/math], [math] q \in \Sigma^*[/math].

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

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


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


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

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


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

Пример

Finite state machine 4.png

Это НКА, который распознает язык из алфавита [math] \lbrace 0, 1 \rbrace [/math], где на четвертой с конца позиции стоит 0.

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

Постановка задачи

Пусть заданы НКА и слово [math]w[/math]. Требуется определить, допускает ли НКА данное слово.

Алгоритм

Определим множество всех достижимых состояний из стартового по слову [math] \alpha [/math] : [math] R(\alpha) = \lbrace p \ | \ \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace [/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] \forall q \in \delta(p, c) [/math].

Теперь, когда мы научились по [math] R(\alpha) [/math] строить [math] R(\alpha c)[/math], возьмем [math] R(\varepsilon) [/math] и будем последовательно вычислять [math]R(w[1 \ldots k])[/math] для [math] k=1 \ldots |w| [/math].

Таким образом, мы получим [math]R(w)[/math], и всё, что осталось — проверить, есть ли в нём терминальное состояние.

Псевдокод

bool accepts([math]\langle \Sigma, Q, s, T, \delta \rangle[/math]: Automaton, [math]\mathtt{w}[/math]: String):
  [math] R_0 = \lbrace s \rbrace [/math]
  for i = 1 to [math]\mathtt{w}[/math].length
     [math] R_i = \varnothing [/math]
     for ([math] q [/math] in [math] R_{i - 1} [/math]) 
         [math] R_i = R_i \cup \delta(q, \mathtt{w}[i]) [/math]
  return [math] R_{|\mathtt{w}|} \cap T \neq \varnothing [/math]

Время работы алгоритма: [math] \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) [/math].

См. также

Источники информации

  • Ю. Громкович Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 2010. — С. 87. — ISBN 978-5-9775-0406-5
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages, and Computation. Second edition. P. 71. ISBN 0-201-02988-X
  • Wikipedia — Nondeterministic finite automaton