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



             

Задачи - часть 2


  • Множество всех слов, в которых букв 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} не является автоматным.




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