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




Задачи


Задача 5.1.

Определите конкатенацию для следующих пар языков L1 и L2:

  • L1= {a, ab, abb} и L2= {?, a, b, ab, a};
  • L1= {?, a, ab, abb} и L2= { a, b, abb, a};
  • L1= {?, a, b, ab, aba} и L2= {?, a, b, ab, ba};

Задача 5.2. Пусть L={baa, bab, bba, bbb}. Какой из следующих языков является итерацией L* этого языка?

  • { w | w=bw' и | w| делится на 3 }
    {?};
  • { w | w=bw' и | w|
    3 }
    {?};
  • { w | w=w1w2w3 … w3n и w3i+1 = b для всех i <n }
    {?};
  • { w | w=bw' и | w|
    12 }.

Задача 5.3. Докажите правильность регулярного выражения в примере 5.4.

Задача 5.4. Докажите следующие эквивалентности для регулярных выражений.

  • p*(p+q)* = (p + qp*)* = (p+q)*;
  • p(qp)* = (pq)*p;
  • (p*q*)* =(q*p*)*;
  • (pq)+(q*p* + q*) = (pq)*p q+p*.

Задача 5.5. Постройте регулярное выражение, задающее язык язык L в алфавите ?= {0, 1}.

  • L= {w | w содержит нечетное число букв 0 и четное число букв 1}};
  • L= {w | w содержит подслово 001 или подслово 110 };
  • L= {w | w содержит по крайней мере мере два подряд идущих 0 };
  • L= {w | w не содержит подслов 011 и 010}.

Задача 5.6. Определите, какой язык представляется следующими регулярными выражениями.

  • (0*1*)0;
  • (01*)0;
  • (00 +11 +(01 + 10)(00 +11)+(01+10))*.

Задача 5.7. Упростить следующие регулярные выражения.

  • (00*)0 + (00)*;
  • (0+1)(? + 00)+ + (0+1);
  • (0 + ?)0*1.

Задача 5.8. Выше в задаче 14.5 предлагалось построить автомат-распознаватель, который проверяет правильность сложения. Постройте регулярное выражение, задающее распознаваемый этим автоматом язык S, т.е. следующее множество слов в алфавите {0, 1}3

S= {(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)}.

Задача 5.9. Пусть Mr - это автомат, который строится в доказательстве теоремы 5.1 по регулярному выражению r. Докажите, что

  • у Mr нет переходов из единственного заключительного состояния qf ;
  • в диаграмме Mr из каждой вершины выходит не более двух ребер;
  • число состояний Mr не более чем вдвое превосходит длину выражения r, т.е. |Q|
    2 |r|.

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

M
из примера 5.7.




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