конспекты занятий по курсам ТРЯП и «Автоматное программирование» Общая часть. Занятие 7. Готовимся к контрольной
7.1. Заданы языки , . Для языка построить однозначную КС-грамматику и детерминированный МП-автомат. Решение обосновать. Решение. Представим как , где , причём Тогда грамматика имеет следующие правила:
| | | |	| |
Здесь порождает слова из , а – слова из . Поскольку и на каждом шаге левого вывода слова из правило однозначно определяется левым нетерминальным символом и двумя символами исходного слова, то грамматика является однозначной. МП-автомат из начального состояния по входному символу переходит в состояние , а по входному символу – в состояние . Из состояния автомат сначала работает так же, как автомат, принимающий язык , переходя в состояние , из которого он считывает . В состоянии автомат сначала считывает , а затем работает так же, как автомат, принимающий язык , и переходит в состояние . Множество заключительных состояний автомата . Правила автомата:
Как видно, для каждой пары либо содержит не более одного элемента для каждого x и Ø, либо = Ø для всех x и содержит не более одного элемента (x – входной символ, z – магазинный символ), т.е. построенный автомат – детерминированный.