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