Введение в схемы, автоматы и алгоритмы

             

Задачи


Задача 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 - автоматный язык в алфавите ?. Доказать, что автоматными являются и следующие языки:

  1. ПРЕФ(L) = {w | существует такое слово x
    ?*, что wx
    L}.
  2. СУФ(L) = {w | существует такое слово x
    ?*, что xw
    L}.
  3. КОР(L) = {w | существуют такие слова x, y
    ?*, что xwy
    L}.
  4. 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 длины
n.

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




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