Applications of Finite State Machines (Алексей Чеусов, LVEE-2019) — различия между версиями
Материал из 0x1.tv
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Batch edit: replace PCRE (\n\n)+(\n) with \2) |
||
(не показаны 24 промежуточные версии этого же участника) | |||
;{{SpeakerInfo}}: {{Speaker|Алексей Чеусов}} <blockquote> In this presentation we define the finite state automata (FSA), Moore and Mealy machines, and Finite State Transducers. We\-ightedWeighted and stochastic finite state machines are described. Also, a few well-known and custom algorithms based on finite state machines, are described. </blockquote> {{VideoSection}} {{vimeoembed|366010077|800|450}} <!-- {{youtubelink|}} --> |Yuxqg35Zjhg}} {{SlidesSection}} [[File:Applications of Finite State Machines (Алексей Чеусов, LVEE-2019).pdf|left|page=-|300px]] {{----}} == Thesis == <latex> fsa\_presentation.pdf}{http://www.mova.org/\textasciitilde\,cheusov/pub/lvee/2019/fsa\_presentation.pdf}. Начать следует с определений и теорем, хорошо знакомых любому выпускнику ВУЗ-а по технической специальности. \textbf{Определение:} Недетерминированным конечным автоматом \linebreak (НКА) называется пятерка \mbox{$<I,S,Q,F,\delta>$}, где \begin{itemize} \item $I$ -- конечное непустое множество символов (алфавит); \item $S$ -- конечное непустое множество состояний; \item $Q$ -- множество стартовых состояний, $Q \subseteq S$; \item $F$ -- множество конечных состояний, $F \subseteq S$; \item $\delta$ -- отношение переходов $\delta \subseteq S \times I \times S$ (или, иначе, $\delta: S \times I \rightarrow 2^S$). \end{itemize} </latex> <latex> Языком КА является множество различных последовательностей символов алфавита, допускаемых конечным автоматом, т.е., цепочек символов вдоль пути от стартового до конечного состояния КА. \textbf{Определение:} Регулярный язык над алфавитом $\Sigma$ определяется следующим образом: \begin{itemize} \item Пустой язык $\emptyset$ и язык $\{\epsilon\}$, состоящий из пустой строки, является регулярным языком; \item $\{a\}$, где $a \in \Sigma$, является регулярным языком; \item Если $A$ и $B$ регулярные языки, то $A \cup B$ (объединение), $A \bullet B$ (конкатенация), и $A\ast$ (звезда Клини) являются регулярными языками; \item Никакие другие языки над $\Sigma$ не являются регулярными. \end{itemize} Этот формализм дает нам так называемые <<регулярные выражения>>. \textbf{Определение:} Детерминированным конечным автоматом \linebreak (ДКА) является пятерка $<I,S,q,F,\delta>$, где \begin{itemize} \item $I$ -- конечное непустое множество символов (алфавит); \item $S$ -- конечное непустое множество состояний; \item $q$ -- стартовое состояние, $q \in S$. \item $F$ -- множество конечных состояний, $F \subseteq S$. \item $\delta$ -- функция переходов: $\delta: S \times I \rightarrow S$ \end{itemize} </latex> <latex> \textbf{Теоремы}: \begin{itemize} \item НКА и ДКА -- эквивалентные формализмы, т.е., для каждого НКА существует эквивалентный ему ДКА, обратное верно по определению. \item В общем случае ДКА может быть экспоненциально больше (по количеству состояний) по сравнению с эквивалентным ему НКА. \item Для любого ДКА существует только один (с точностью до изоморфизма) минимальный ДКА, эквивалентный ему. \item Регулярные языки и конечные автоматы -- эквивалентные формализмы, то есть, для любого КА существует эквивалентный ему регулярный язык и наоборот. \item Конечные автоматы замкнуты относительно операций объединения, вычитания, пересечения, дополнения и звезды Клини. \end{itemize} </latex> ----- <latex> \textbf{Алгоритм} построения ДКА из НКА представлен ниже. ~ ~ \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> ---- <latex> Введем два дополнительных оператора: \begin{itemize} \item R -- оператор инвертирования. $L(R(KA)) = \{inverse(w) | w \in L(KA)\}$ \item D -- оператор построения ДКА по НКА. \end{itemize} \textbf{Алгоритм} Бжозовского построения минимального ДКА по \linebreak НКА:\\ $MinDFA = (D \circ R \circ D \circ R) KA$ \textbf{Замечание:} В отличие от большинства других алгоритмов построения минимального ДКА, алгоритм Бжозовского строит минимальный ДКА по НКА! \newpage Алгоритм проверки, входит ли строка в язык ДКА. </latex> <latex> \begin{algorithm}[h!] \DontPrintSemicolon \SetKwInOut{Input}{input} \SetKwInOut{Output}{output} \Input{DFA = $<I,S,q,F,\delta>, Text=[t_1, t_2 \dots t_n], t_i \in I$} \Output{$true$ \textbf{or} $false$} \SetAlgoLined % \SetAlgoNoEnd $state := q$\; \For{$i$ from $1$ to $n$}{ \item $O$ -- выходной алфавит, конечное непустое множество выходных символов; \item $S$ -- конечное непустое множество состояний; \item $Q$ -- множество стартовых состояний, $Q \subseteq S$; \item $F$ -- множество конечных состояний, $F \subseteq S$; \item $\delta$ -- отношение переходов $\delta \subseteq S \times (I \cup \{\epsilon\}) \times (O \cup \{\epsilon\})\times S$, где $\epsilon$ -- это пустая строка. \end{itemize} \textbf{Замечание:} Взвешенный конечно-автоматный преобразователь \linebreak определяется аналогично взвешенному конечному автомату. \break</latex> <latex> \textbf{Область применения взвешенных конечно-автоматных преобразователей:} распознавание речи, синтез речи, распознавание символов, машинный перевод, различные задачи обработки естественного языка, включая синтаксический анализ и моделирование языка, распознавание образов и вычислительная биология. Задачи, решаемые с помощью конечных автоматов: \begin{itemize} \item Исправление ошибок OCR-распознавания CUSIP (\href{https://en.wikipedia.org/wiki/CUSIP}{https://en. wikipedia.org/wiki/CUSIP}). Идея алгоритма воспользоваться информацией о том, из каких состояний исходного НКА <<сформировано>> состояние ДКА. Эта информация используется для формирования символа выходного алфавита, соответствующего <<конечному>> состоянию, которое соответствует любому набору исходных регулярных выражений. Потенциально выходной алфавит может содержать $2^n$ элементов, где $n$ -- количество исходных регулярных выражений. \end{itemize} </latex> {{----}} [[File:{{#setmainimage:Applications of Finite State Machines (Алексей Чеусов, LVEE-2019)!.jpg}}|center|640px]] {{LinksSection}} * Прежде всего хочется сказать, что данная статья является дополнением к презентации, доступной на сайте \url{http://lvee.org} \linebreak или по ссылке ~ \href{http://www.mova.org/~cheusov/pub/lvee/2019/fsa_presentation.pdf * [ Talks page] <!-- <blockquote>[©]</blockquote> --> {{fblink|2427332600853080}} {{vklink|1456}} <references/> {{stats|disqus_comments=1|refresh_time=2021-08-31T16:13:00.591899|vimeo_plays=11|youtube_comments=0|youtube_plays=61}} [[Категория:LVEE-2019]] [[Категория:Draft]]Finite State Machines]] |
Текущая версия на 12:18, 4 сентября 2021
- Докладчик
- Алексей Чеусов
In this presentation we define the finite state automata (FSA), Moore and Mealy machines, and Finite State Transducers. Weighted and stochastic finite state machines are described. Also, a few well-known and custom algorithms based on finite state machines, are described.
Содержание
Видео
Презентация
Thesis
Примечания и ссылки
- Прежде всего хочется сказать, что данная статья является дополнением к презентации, доступной по ссылке ~
http://www.mova.org/~cheusov/pub/lvee/2019/fsa_presentation.pdf
- [ Talks page]
- Discuss on Facebook
- Discuss on VK
Plays:72
Comments:1