Да се докаже, че L не е автоматен език

[Mimiinka]

Трябва да се решат тези задачи или поне 3 от тях :

Задача 1. Дадена е азбуката  = {a,b}. Конструирайте ДКА, разпознаващ езика:
L = {w | w има нечетен брой b-та и започва с ab}.

Задача 2. Конструирате ДКА, еквивалентен на недетерминирания автомат A = (Q,, , q0, F),
където Q = {q0, q1, q2},  = {a, b}, F = {q2} и  е зададена с таблицата:
a b
q0 {q0} {q1, q2}
q1 {q1, q2} {q1}
q2 {q1} {q0, q2}

Задача 3. Граматиката G, пораждаща аритметични ирази, е зададена с правилата:
E ! T + E | T − E | T
T ! F × T | F : T | F
F ! (E) | 0 | 1 | 2 | · · · | 9.
Определете
а) множеството N от нетерминалните символи на G и стартовия нетерминал;
б) множеството  от терминалните символи на G;
в) дървото на извод за аритметичния израз 7 + 3 × (6 − 2) : 4 и стойността му.

Задача 4. Даден е езикът
L = {! | ! 2 {a, b} и ! съдържа като поддума bab}.
а) Да се построи НДКА, който го разпознава.
б) Да се конструира автоматна граматика, която го поражда.

Задача 5. Даден е езикът
L = {1n0
2n | n 2 N0}.
а) Да се докаже, че L не е автоматен език.
б) Да се докаже, че L e контекстно-свободен език.

Благодаря !