Контрольная работа по теории языков программирования и методам трансляции

Задание 1
Порождает ли выражение (ab)*(ba)* тот же язык, что распознаётся ДКА M = ({A,B,C,D}, {a,b}, , A,{A,D,E}), где функция переходов задана следующим образом:
(A, a) =B, (A, b) =C, (B, b) =D, (C, a) =E,
(D, a) =B, (D, b) =C, (E, b) =C.
Задание 2
Заданы грамматика G={{A,B,C,D,E,F}, {a,b},{SAB|C; AAE|a;
EaE|; BbB|Bb|b; CCD; Fab; Daba}, S}
и MA M={{q}, {a,b}, {S,a,b,A,B}, { (q,, S) =
{(q, AB)}, (q, , A) ={(q, aA), (q, a)}, (q, , B) ={(q, bB), (q, b)}, (q, a, a) ={(q, )}, (q, b, b) = {(q, )}, q, S},
принимающий слова опустошением магазина.
i. Эквивалентны ли грамматика G и N-автомат M?
ii. Однозначна ли грамматика G? Если нет, то постройте эквивалентную ей однозначную грамматику.
iii. Является ли автомат M детерминированным? Если нет, постройте эквивалентный ему детерминированный МА.
Задание 3
Заданы языки ,
. Для языка построить однозначную КС-грамматику и детерминированный МП-автомат. Решение обосновать.