Задачи

Задача 6.1. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный построенному выше в примере 6.2 НКА M.

Задача 6.2. Цилиндрификация - это операция, которая обратна проекции. Для любых алфавитов ? и ? таких, что ?

?, и любого языка L в алфавите ? определим его цилиндрификацию как язык CYL?(L) = {w

?* | при вычеркивании из w всех букв, не входящих в ?, получается слово u

L).

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

Задача 6.3.

Обращением слова w=w1w2 … wk (wi

?, i=1, … , k) называется слово w{-1}= wk … w2 w1. Показать, что для автоматного языка L его обращение - язык L{-1} ={ w{-1} | w

L} также является автоматным языком.

Задача 6.4.

Пусть L - автоматный язык в алфавите ?. Доказать, что автоматными являются и следующие языки:

ПРЕФ(L) = {w | существует такое слово x
?*, что wx
L}.
СУФ(L) = {w | существует такое слово x
?*, что xw
L}.
КОР(L) = {w | существуют такие слова x, y
?*, что xwy
L}.
MAX(L) = {w | w
L и для всякого непустого x слово wx
L}.

Задача 6.5. Пусть L - автоматный язык в алфавите ?={a1,…, am}, а L1,…, Lm - это автоматные языки в алфавите ?. Доказать, что автоматным является и язык ЗАМ(L), полученный из слов L заменой каждой буквы ai на некоторое слово из Li, т.е. ЗАМ(L) = {w | textit{ существует такое слово }u=a{i1}a{i2}… a{in}

L и такие слова w1,w2,…, wn

?*, что w=w1w2… wn и wj

L{ij} для всех j=1,2,… n }.

Задача 6.6. Пусть L - автоматный язык в алфавите ?, k - целое положительное число и

- отображение ?k в ?. Доказать, что автоматным является язык L1 ={

(a1a2… ak) …

(a{(n-1)k+1}a(n-1)k+2 … ank) | a1a2… ank

L}.

Задача 6.7. Докажите, что теорема 6.3 о разрастании остается справедливой и при замене условия 1) |xy|

n на условие 1') |yz|

n, т.е. повторяющееся подслово y имеется и в суффиксе w длины

Задача 6.8. Доказать, что следующие языки в алфавите ? ={a, b, c} не являются автоматными.

Содержание Назад Вперед