Математическая теория формальных языков
автомата эквивалентны, если они распознают
Пример 10.1.15.
Пусть - МП-автомат из примера 10.1.2. Тогда .
Пример 10.1.16.
Пусть . Рассмотрим МП-автомат , где , , I = {1}, F = {4,5} и
Тогда .
Определение 10.1.17.
Два МП- автомата эквивалентны, если они распознают один и тот же язык.
Замечание 10.1.18.
В данном пособии не рассматриваются преобразователи с магазинной памятью (pushdown transducer) обобщение автоматов с магазинной памятью посредством добавления "выходного" потока (см. [7, 3.5] или [2, 3.1.4]).
Замечание 10.1.19.
Некоторые авторы изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния
и
и последовательность , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.20.
Некоторые авторы добавляют в определение МП-автомата седьмую компоненту - Z0, называемую маркером магазинной памяти (start pushdown symbol), и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния
и , что . Такое определение не изменяет класса языков, распознаваемых МП-автоматами.
Замечание 10.1.21.
Класс языков, распознаваемых МП-автоматами, не изменится также, если использовать следующую естественную комбинацию двух предыдущих определений: слово w допускается МП-автоматом , если найдутся такие состояния
и
и последовательность , что .
Замечание 10.1.22.
Некоторые авторы добавляют в определение МП-автомата маркер магазинной памяти Z0, отбрасывают множество F и изменяют определение допускаемых слов следующим образом: слово w допускается МП-автоматом , если найдутся такие состояния
и , что . Это также не изменяет класса языков, распознаваемых МП-автоматами.
Упражнение 10.1.23. Найти МП-автомат, распознающий язык
Упражнение 10.1.24. Найти МП-автомат, распознающий язык
Упражнение 10.1.25. Найти МП-автомат, распознающий язык
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий