Список заданий по ТФЯ 2015

Материал из Викиконспекты
Перейти к: навигация, поиск

<wikitex>

Теория формальных языков, 5 семестр

  1. Построить конечный автомат для языка слов над бинарным алфавитом, в которых четность числа 0 равна четности числа 1
  2. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3
  3. Построить конечный автомат для языка слов над бинарным алфавитом, в которых нет трех нулей подряд
  4. Построить конечный автомат для языка слов над бинарным алфавитом, которые представляют собой двоичную запись чисел, кратных 5
  5. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей не кратно 3
  6. Построить конечный автомат для языка слов над бинарным алфавитом, в которых есть три нуля подряд. Сделайте вывод из последних двух заданий.
  7. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 и которые представляют собой двоичную запись чисел кратных 5.
  8. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число нулей кратно 3 или которые представляют собой двоичную запись чисел кратных 5. Сделайте вывод из последних двух заданий.
  9. Построить конечный автомат для языка слов над бинарным алфавитом, в пятый символ с конца - 0. Можно построить недетерминированный автомат.
  10. Постройте детерминированный автомат для предыдущего задания или докажите, что в нем слишком много состояний, чтобы его рисовать ;).
  11. Постройте регулярное выражение для языка слов над бинарным алфавитом, в которых нет двух нулей подряд.
  12. Построить конечный автомат для языка слов над бинарным алфавитом, в которых число 0 кратно 3.
  13. ХМУ 4.2.2, стр 163
  14. ХМУ 4.2.3, стр 163
  15. ХМУ 2.3.1, стр 83
  16. Докажите, что минимальный ДКА для языка $(0|1)^*0(0|1)^k$ содержит минимум $2^k$ состояний
  17. ХМУ 4.2.4, стр 163
  18. ХМУ 4.2.5, стр 164
  19. ХМУ 4.2.6, стр 164
  20. ХМУ 4.2.7, стр 164
  21. ХМУ 4.2.8, стр 164
  22. ХМУ 4.2.10, стр 165
  23. ХМУ 4.2.11, стр 165
  24. Доказать нерегулярность языка слов $0^n1^n$
  25. Доказать нерегулярность языка, каждое слово которого содержит поровну 0 и 1.
  26. Доказать нерегулярность языка палиндромов.
  27. Доказать нерегулярность языка тандемных повторов.
  28. Доказать нерегулярность языка $0^n1^m$, $n \le m$
  29. Доказать нерегулярность языка $0^n1^m$, $n \ne m$
  30. Доказать нерегулярность языка $0^{n^2}$
  31. Доказать нерегулярность языка $0^p$, $p$ — простое
  32. Доказать нерегулярность языка двоичных записей простых чисел
  33. Доказать нерегулярность языка $0^n1^m$, $gcd(n, m) = 1$
  34. Доказать нерегулярность языка $0^a1^b2^c$, $a \ne b$ и $b \ne c$
  35. Приведите пример нерегулярного языка, для которого выполнена лемма о разрастании