editor
177
правок
Изменения
м
Пунктуация и орфография
Для <tex> D_i </tex> существует рекуррентная формула:
* <tex> D_i = D_{i - 1} \cup \lbrace \langle p, q \rangle | \exists c \in \Sigma : \langle \delta(p, c), \delta(q, c) \rangle \in E_{i - 1} \rbrace </tex>
То есть <tex> D_i </tex> {{---}} объединение множества всех пар состояний, которые различаются строками длины меньшими , меньшей <tex> i </tex>, с множеством всех пар состояний, которые различаются строками длины ровно <tex> i </tex>
Заметим, что <tex> \exists k : E_k = \varnothing </tex>, причем <tex> k \le |Q| ^ 2</tex>. И еще заметим, что <tex> E_k = \varnothing \Rightarrow E_{k + 1} = \varnothing </tex>, так как в <tex> D_{k+1}</tex> новых элементов не добавится, поэтому <tex> D_{k+1} = D_k </tex>.
Будем строить <tex> D_i </tex> в порядке увеличения <tex> i </tex>, пока <tex> D_i \neq D_{i - 1}</tex>.
Заметим, что <tex> D_0 = \lbrace \langle p, q\rangle | p \in T_1 \Leftrightarrow q \notin T_2 \rbrace </tex>, так как строка длины 0 одна, {{---}} это <tex> \varepsilon </tex>, а <tex> \varepsilon </tex> различает только пары состоящие из одного терминального состояния и одного нетерминального.
Дальше будем получать <tex> D_i </tex> по рекуррентной формуле , пока не выполнится условие остановки.
Это можно реализовать проще: будем хранить для каждого состояния, из какого состояние состояния есть переход по символу <tex> c </tex> в наше. В очередь будем класть пары неэквивалентных состояний. Дальше вытаскивая из очереди пару, рассмотрим все пары состояний, из которых есть переход по одинаковому символу в элементы пары из очереди. Пометим их неэквивалентными и положим в очередь. Псевдокод:
<font size = 3>
<tex> q = \varnothing </tex>
