Недетерминированные конечные автоматы — различия между версиями
(→Язык автомата) |
м (rollbackEdits.php mass rollback) |
||
(не показано 28 промежуточных версий 11 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Недетерминированный конечный автомат''' ( | + | '''Недетерминированный конечный автомат (НКА)''' (англ. ''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 = | ||
− | ''' | + | '''Мгновенное описание''' (англ. ''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>. |
}} | }} | ||
− | |||
− | |||
− | |||
== Язык автомата == | == Язык автомата == | ||
Строка 38: | Строка 38: | ||
|definition = | |definition = | ||
Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>. | Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>. | ||
− | <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>. | ||
}} | }} | ||
− | Язык НКА | + | Язык НКА является автоматным языком, так как для любого НКА можно [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона|построить эквивалентный ему ДКА]], а значит, вычислительная мощность этих двух автоматов совпадает. |
== Пример == | == Пример == | ||
− | [[Файл: | + | [[Файл: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> R(\varepsilon) = \lbrace s \rbrace </tex>. Пусть мы построили <tex> R(\alpha) </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> \forall q \in \delta(p, c) </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>, и всё, что осталось — проверить, есть ли в нём терминальное состояние. |
− | < | + | |
− | + | ===Псевдокод=== | |
− | + | '''bool''' accepts(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex>: '''Automaton''', <tex>\mathtt{w}</tex>: '''String'''): | |
− | + | <tex> R_0 = \lbrace s \rbrace </tex> | |
− | + | '''for''' i = 1 '''to''' <tex>\mathtt{w}</tex>.length | |
− | + | <tex> R_i = \varnothing </tex> | |
− | + | '''for''' (<tex> q </tex> '''in''' <tex> R_{i - 1} </tex>) | |
− | + | <tex> R_i = R_i \cup \delta(q, \mathtt{w}[i]) </tex> | |
− | + | '''return''' <tex> R_{|\mathtt{w}|} \cap T \neq \varnothing </tex> | |
− | |||
− | |||
Время работы алгоритма: <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. — С. 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) — пятёрка ДКА — существование нескольких переходов по одному символу из одного состояния. | , где — алфавит, — множество состояний автомата, — начальное состояние автомата, — множество допускающих состояний автомата, — функция переходов. Таким образом, единственное отличие НКА от
Процесс допуска
НКА допускает слово
, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово . Теперь это опишем более формально.Определение: |
Мгновенное описание (англ. snapshot) — пара | , , .
Определим некоторые операции для мгновенных описаний.
Определение: |
Говорят, что
| выводится за один шаг (англ. directly yields) из , если:
Определение: |
Рефлексивно-транзитивное замыкание отношения обозначается как . И говорят, что выводится за ноль и более шагов (англ. yields) из , если . |
Определение: |
НКА допускает (англ. accepts) слово | , если .
Язык автомата
Определение: |
Множество слов, допускаемых автоматом
| , называется языком НКА .
Язык НКА является автоматным языком, так как для любого НКА можно построить эквивалентный ему ДКА, а значит, вычислительная мощность этих двух автоматов совпадает.
Пример
Алгоритм, определяющий допустимость автоматом слова
Постановка задачи
Пусть заданы НКА и слово
. Требуется определить, допускает ли НКА данное слово.Алгоритм
Определим множество всех достижимых состояний из стартового по слову
: .Заметим, что если
, то слово допускается, так как по определению . Таким образом, алгоритм состоит в том, чтобы построить .Очевидно, что
. Пусть мы построили , построим , где . Заметим, что , так как, .
Теперь, когда мы научились по
строить , возьмем и будем последовательно вычислять для .Таким образом, мы получим
, и всё, что осталось — проверить, есть ли в нём терминальное состояние.Псевдокод
bool accepts(: Automaton, : String): for i = 1 to .length for ( in ) return
Время работы алгоритма:
.См. также
Источники информации
- Ю. Громкович Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию: Пер. с нем. — СПб.:БХВ-Петербург, 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