онечный автомат

ћатериал из Ёнциклопедии в свободной энциклопедии
(перенаправлено с « онечные автоматы»)
ѕерейти к: навигаци€, поиск

 онечный автомат в абстрактный автомат, число возможных состо€ний которого конечно. –езультат работы автомата определ€етс€ по его конечному состо€нию.

—уществуют различные способы задани€ конечного автомата. Ќапример, конечный автомат может быть задан в виде упор€доченной п€терки: ~M = (V, Q, q_0, F, \delta) , где

  • V в входной алфавит (конечное множество входных символов), из которого формируютс€ входные цепочки, допускаемые конечным автоматом;
  • Q в множество состо€ний;
  • q_0 в начальное состо€ние (q_0 \in Q);
  • F в множество заключительных состо€ний (F \subset Q);
  • \delta в функци€ переходов, определенна€ как отображение \delta : Q \times ( V \cup \{ \lambda \} ) \rightarrow Q, такое, что \delta(q,a) = \{ r : q \rightarrow_a r \}, то есть значение функции переходов на упор€доченной паре (состо€ние, входной символ или пуста€ цепочка) есть множество всех состо€ний, в которые из данного состо€ни€ возможен переход по данному входному символу или пустой цепочке (λ).

 онечный автомат начинает работу в состо€нии q0, считыва€ по одному символу входной цепочки. —читанный символ переводит автомат в новое состо€ние в соответствии с функцией переходов. „ита€ входную цепочку x и дела€ один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажетс€ в каком-то состо€нии q'. ≈сли это состо€ние €вл€етс€ заключительным, то говор€т, что автомат допустил цепочку x.

 онечные автоматы широко используютс€ на практике, например, в синтаксических и лексических анализаторах, тестировании программного обеспечени€ на основе моделей.

ƒругие способы описани€[править | править Ёнцикло-текст]

  1. ƒиаграмма состо€ний (или иногда граф переходов) в графическое представление множества состо€ний и функции переходов. ѕредставл€ет собой размеченный ориентированный граф, вершины которого в состо€ни€  ј, дуги в переходы из одного состо€ни€ в другое, а метки дуг в символы, по которым осуществл€етс€ переход из одного состо€ни€ в другое. ≈сли переход из состо€ни€ q1 в q2 может быть осуществлен по одному из нескольких символов, то все они должны быть надписаны над дугой диаграммы.
  2. “аблица переходов в табличное представление функции δ. ќбычно в такой таблице каждой строке соответствует одно состо€ние, а столбцу в один допустимый входной символ. ¬ €чейке на пересечении строки и столбца записываетс€ состо€ние, в которое должен перейти автомат, если в данном состо€нии он считал данный входной символ.

ƒетерминированность[править | править Ёнцикло-текст]

 онечные автоматы подраздел€ютс€ на детерминированные и недетерминированные.

ƒетерминированный конечный автомат
  • ƒетерминированным конечным автоматом (ƒ ј) называетс€ такой автомат, в котором нет дуг с меткой ε (предложение, не содержащее ни одного символа), и из любого состо€ни€ по любому символу возможен переход в точности в одно состо€ние.
  • Ќедетерминированный конечный автомат (Ќ ј) €вл€етс€ обобщением детерминированного. Ќедетерминированность автоматов достигаетс€ двум€ способами:
—уществуют переходы, помеченные пустой цепочкой ε »з одного состо€ни€ выходит несколько переходов, помеченных одним и тем же символом
Ќ ј с e.jpg
Ќ ј без e.jpg

≈сли рассмотреть случай, когда автомат задан следующим образом: ~M = (V, Q, S, F, \delta), где S в множество начальных состо€ний автомата, такое, что S \subseteq V, то по€вл€етс€ третий признак недетерминированности в наличие нескольких начальных (стартовых) состо€ний у автомата ~M.


“еорема о детерминизации утверждает, что дл€ любого конечного автомата может быть построен эквивалентный ему детерминированный конечный автомат (два конечных автомата называют эквивалентными, если их €зыки совпадают). ќднако поскольку количество состо€ний в эквивалентном ƒ ј в худшем случае растЄт экспоненциально с ростом количества состо€ний исходного Ќ ј, на практике подобна€ детерминизаци€ не всегда возможна.  роме того, конечные автоматы с выходом в общем случае не поддаютс€ детерминизации.

¬ силу последних двух замечаний, несмотр€ на бо́льшую сложность недетерминированных конечных автоматов, дл€ задач, св€занных с обработкой текста, преимущественно примен€ютс€ именно Ќ ј.

јвтоматы и регул€рные €зыки[править | править Ёнцикло-текст]

ƒл€ конечного автомата можно определить €зык (множество слов) в алфавите V, который он допускает в так называютс€ слова, чтение которых переводит автомат из начального состо€ни€ в одно из заключительных состо€ний.

“еорема  лини утверждает, что €зык €вл€етс€ регул€рным тогда и только тогда, когда он допускаетс€ некоторым конечным автоматом, используемым в этом €зыке.

—пециализированные €зыки программировани€[править | править Ёнцикло-текст]

¬ SFC программа описываетс€ в виде схематической последовательности шагов, объединенных переходами.

–азработка моделей с использованием конечных автоматов[править | править Ёнцикло-текст]

 онечные автоматы позвол€ют построить модели систем параллельной обработки, однако, чтобы изменить число параллельных процессов в такой модели требуетс€ внести существенные изменени€ в саму модель.  роме того, попытка разработки сложной модели на конечном автомате приведет к быстрому росту числа состо€ний автомата, что в итоге сделает разработку такой модели крайне утомительным зан€тием.  ак было отмечено выше, последнюю проблему можно решить, если использовать недетерминированный автомат.

ѕримечани€[править | править Ёнцикло-текст]

—м. также[править | править Ёнцикло-текст]

—сылки[править | править Ёнцикло-текст]

Ћитература[править | править Ёнцикло-текст]

  • Ѕелоусов ј. »., “качев —. Ѕ. ƒискретна€ математика. в ћ.: ћ√“”, 2006. в —. 460-587. в ISBN 5-7038-2886-4.