Проблема эквивалентности конечных автоматов

Теорема 15.6.1.

Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G1 и G2

узнать, верно ли, что .

Теорема 15.6.2.

Существует алгоритм, позволяющий по произвольным двум праволинейным грамматикам G1 и G2

узнать, верно ли, что L(G1) = L(G2).

Упражнение 15.6.3.

Эквивалентны ли грамматика

и грамматика