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

Примените процедуру детерминизации из теоремы


Задача 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} не являются автоматными.
  • Множество всех слов, в которых букв a на 3 больше, чем букв b.
  • L={ ancbm | m > 3n }.
  • L={ wcw-1 | w =a2bna для некоторого n > 0}.
  • L={ w | |w| = 2n для некоторого целого числа n }.
  • L={ wc|w| | w
    {a,b}*, |w| - длина слова w}.

Задача 6.9. ?-выражение - это либо переменная x, или символ ?, за которым следует переменная, а далее либо ?-выражение, либо левая скобка, ?-выражение, еще одно ?-выражение и правая скобка. Например, ? x x, ? x(x x), ? x ? x (? x(x x) ? x(x x)) - это правильные ?-выражения, а (x x), ? x(? x) и ? x((x x) - неправильные. Докажите, что язык ?-выражений в алфавите { x, ?, (, ) } не является автоматным.
Задача 6.10. Выше в задаче строился автомат-распознаватель, который проверял правильность сложения двоичных чисел. Докажите, что для операции умножения двоичных чисел такого автомата не существует, т.е. что язык в алфавите троек битов U = {(x1(1),x2(1),y(1)) (x1(2),x2(2),y(2)) … (x1(n),x2(n),y(n)) | y = y(n) … y(2)y(1) - это первые n битов произведения двоичных чисел x1= x1(n)… x1(2)x1(1) и x2 = x2(n)… x2(2)x2(1)} не является автоматным.
Задача 6.11.
Доказать, что язык L = { w | число букв a в w
число букв b в w } в алфавите ? ={a, b} не является автоматным.

Содержание раздела