Задача 6.1. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный построенному выше в примере 6.2 НКА M.
Задача 6.2. Цилиндрификация - это операция, которая обратна проекции. Для любых алфавитов ? и ? таких, что ?
Показать, что для автоматного языка L язык CYL?(L) также является автоматным языком. Предложите процедуру перестройки автомата, распознающего L , в автомат, распознающий CYL?(L).
Задача 6.3.
Обращением слова w=w1w2 … wk (wi
Задача 6.4.
Пусть L - автоматный язык в алфавите ?. Доказать, что автоматными являются и следующие языки:
Задача 6.5. Пусть L - автоматный язык в алфавите ?={a1,…, am}, а L1,…, Lm - это автоматные языки в алфавите ?. Доказать, что автоматным является и язык ЗАМ(L), полученный из слов L заменой каждой буквы ai на некоторое слово из Li, т.е. ЗАМ(L) = {w | textit{ существует такое слово }u=a{i1}a{i2}… a{in}
Задача 6.6. Пусть L - автоматный язык в алфавите ?, k - целое положительное число и
Задача 6.7. Докажите, что теорема 6.3 о разрастании остается справедливой и при замене условия 1) |xy|
Задача 6.8. Доказать, что следующие языки в алфавите ? ={a, b, c} не являются автоматными.