По праволинейной грамматике построить конечный автомат, определяющий такой же язык (см. стр. 7) и. 2

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

I → aB | bB | bA
A → aI | bA | λ
B → aB | bC
C → aB
Приводим к автоматному виду (F – «конец строки»):
I → aB | bB | bA
A → aI | bA | λF
B → aB | bC
C → aB
Так как пустой переход ведет только из A в F, то A является «концом строки» и необходимость в F отсутствует.
Граф недетерминированного автомата:
Входное слово «bbab»:
({I},bbab) |-- ({A,B}, bab) |-- ({A,C},ab) |-- ({I,B},b) |-- ({A,C},λ)
Среди состояний (в которых находится недерминированный автомат после того, как цепочка закончилась) есть заключительное A, следовательно, цепочка принята автоматом.
Детерминируем автомат.
вход
a b
{I} B A,B
{B} B C
{A,B} I,B A,C
{C} B
{I,B} B A,B,C
{A,C} I,B A
{A,B,C} I,B A,C
{A} I A
Переименуем состояния