Математическая теория формальных языков
состоящий из меток всех успешных
Определение 2.1.12.
Язык, распознаваемый конечным автоматом M, - это язык L(M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает (recognizes, accepts) язык L(M).
Замечание 2.1.13.
Если , то язык, распознаваемый конечным автоматом , содержит .
Пример 2.1.14.
Пусть , где Q = {1,2}, , I = {1}, F = {1,2},
Тогда
Определение 2.1.15.
Два конечных автомата эквивалентны, если они распознают один и тот же язык.
Определение 2.1.16.
Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.
Замечание 2.1.17.
Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).
Пример 2.1.18.
Рассмотрим однобуквенный алфавит . При любых фиксированных
и
язык
является автоматным.
Замечание 2.1.19.
Каждый конечный язык является автоматным.
Определение 2.1.20.
Состояние q достижимо (reachable) из состояния p, если существует путь, началом которого является p, а концом - q.
Лемма 2.1.21.
Каждый автоматный язык распознается некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.
Пример 2.1.22.
Рассмотрим конечный автомат , где Q = {1,2,3,4}, , I = {1,2,4}, F = {1,3,4},
Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требованиям леммы 2.1.21. Получается эквивалентный конечный автомат , где Q' = {1,4}, I' = {1,4}, F' = {1,4},
Замечание 2.1.23
Естественным обобщением конечного автомата является конечный преобразователь (finite-state transducer), позволяющий на каждом такте отправить несколько символов в дополнительный "выходной" поток. В некоторых книгах конечными автоматами называют именно такие устройства (с выходным потоком).
В данном пособии конечные преобразователи рассматриваться не будут.
Упражнение 2.1.24. Найти конечный автомат, распознающий язык
Упражнение 2.1.25. Найти конечный автомат, распознающий язык
Упражнение 2.1.26. Найти конечный автомат, распознающий язык
Упражнение 2.1.27. Найти конечный автомат, распознающий язык
Упражнение 2.1.28. Найти конечный автомат, распознающий язык
Упражнение 2.1.28. Найти конечный автомат, распознающий язык , где ,
и
для любого
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий