Участник:StasFomin/A — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
<latex> 111 \begin{algorithm}[h!] \DontPrintSemicolon \SetKwInOut{Input}{input} \SetKwInOut{Output}{output} \Input{NFA = $<I,S,Q,F,\delta>$} \Output{DFA = $<I,S^{\prime},q^\prime,F^{\prime},\delta^{\prime}>$} \SetAlgoLined % \SetAlgoNoEnd $\delta^\prime := \emptyset, q^\prime := \{s | s \in Q\}, S^\prime := \{q^\prime\}$\; $seen := \{q^\prime\}, queue := [q^\prime]$\; \While{$queue \neq \emptyset$}{ $src\_states \leftarrow queue$\; \For{$i \in I$}{ $trg\_states := \{s^{trg} | (s^{src},i,s^{trg}) \in \delta, s^{src} \in src\_states\}$\; \If{$trg\_states \neq \emptyset$}{ $\delta^\prime \leftarrow (src\_states, i, trg\_states)$\; $S^\prime \leftarrow trg\_states$\; \If{$trg\_states \notin seen$}{ $queue \leftarrow trg\_states$\; $seen \leftarrow trg\_states$\; } } } } $F^\prime := \{state\_set \in S^\prime | \exists s \in state\_set, s \in F\}$ \caption{nfa2dfa algorithm AKA <<Subset construction>>} \end{algorithm} </latex>[[Файл:2019-lvee miet kai gav ei rdp.pdf|640px|center|frame|11111]] |