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

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

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