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