По праволинейной грамматике построить конечный автомат. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по микропроцессорной технике
По праволинейной грамматике построить конечный автомат

По праволинейной грамматике построить конечный автомат .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

По праволинейной грамматике построить конечный автомат, определяющий такой же язык (см. стр. 7) и продемонстрировать его работу на каком-нибудь входном слове. Детерминировать получившийся автомат (см. стр. 6-7). По детерминированному автомату составить праволинейную грамматику, эквивалентную исходной. I → aI | bA | bC, A → bI | bB | b, B → a | bA | b, C → aA | b;

Решение

Потяни, чтобы посмотреть

I → aI | bA | bC
A → bI | bB | b
B → a | bA | b
C → aA | b
Приводим к автоматному виду (F – «конец строки»):
I → aI | bA | bC
A → bI | bB | bF
B → aF | bA | bF
C → aA | bF
Граф недетерминированного автомата:
Входное слово «babbba»:
({I},babbba) |-- ({A,C},abbba) |-- ({A},bbba) |-- ({I,B,F},bba) |-- ({A,C,F},ba) |-- ({I,B,F},a) |-- ({I,F},λ)
Среди состояний (в которых находится недерминированный автомат после того, как цепочка закончилась) есть заключительное F, следовательно цепочка принята автоматом.
Детерминируем автомат.
вход
a b
{I} I A,C
{A}
I,B,F
{B} F A,F
{C} A F
{F}
{I,A} I I,A,B,C,F
{I,B} I,F A,C,F
{I,C} I,A A,C,F
{I,F} I A,C
{A,B} F I,B,F
{A,C} A I,B,F
{A,F}
I,B,F
{B,C} A,F A,F
{B,F} F A,F
{C,F} A F
{I,A,B} I,F I,A,B,C,F
{I,A,C} I,A I,A,B,C,F
{I,A,F} I I,A,B,C,F
{I,B,C} I,A,F A,C,F
{I,B,F} I,F A,C,F
{I,C,F} I,A A,C,F
{A,B,C} A,F I,B,F
{A,B,F} F I,B,F
{A,C,F} A I,B,F
{B,C,F} A,F A,F
{I,A,B,C} I,A,F I,A,B,C,F
{I,A,B,F} I,F I,A,B,C,F
{I,A,C,F} I,A I,A,B,C,F
{I,B,C,F} I,A,F A,C,F
{A,B,C,F} A,F I,B,F
{I,A,B,C,F} I,A,F I,A,B,C,F
Состояния {I,B}, {I,C}, {A,B}, {I,A,B}, {I,A,C}, {I,B,C}, {I,A,B,C} недостижимы из начального, удалим их и переименуем остальные состояния

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу