fl_task4 (1178891), страница 2
Текст из файла (страница 2)
В случае, если автомат A не является полным, пополним автомат A,Σдобавив состояние qD , такое что qD −→ qD , и если δ(q, σ) = ∅, то теперьδ(q, σ) = qD . Если в A есть состояния, не достижимые из начальногосостояния, удалим их.2. Разделим множество состояний на два подмножества: множество принимающих состояний F = Q1 и его дополнение Q \ F = Q2 .i + 1. Пусть после i-ого шага алгоритма множество состояний Q разбитона j подмножеств Q1 , . . .
, Qj . Зафиксируем символ σ ∈ Σ сделаем следуσющее. Если для qk ∈ Qk qk →− ql ∈ Ql , поместим состояние qk в множествоQk,l . Получили новое разбиение Q на подмножества Qk,l и повторяем длянего эту процедуру для оставшихся символов σ ∈ Σ. Если после |Σ| разбиений мы получили разбиение, в котором j подмножеств, то алгоритмостанавливается, в противном случае он продолжает работу.6Склеив все состояния, попавшие в одно подмножество, получим минимальный автомат.Упражнение 3. Доказать корректность данного алгоритма.3ЗадачиЗадача 4. Доказать, что для языка L выполняется лемма о накачке, ноон не является регулярным. Обозначим за PRIMES множество простыхчисел. Напомним, что A+ = AA∗ .L = b∗ ∪ {ab p | p ∈ PRIMES} ∪ aa+ b∗ .Задача 5 (№6 из задания).
Будут ли регулярными следующие языки:1. L1 = {a2013n+5 | n = 0, 1, . . .} ∩ {a509k+29 | k = 401, 402, . . .} ⊆ {a∗ }2 +12. L2 = {a200n| n = 1000, 1001, . . .} ⊆ {a∗ }3. Язык L3 всех слов в алфавите 0, 1, которые представляют числа в двоичной записи, дающие остаток два при делении на три (слово читаетсясо старших разрядов). Например, 001010(10102 = 1010 = 3 × 3 + 1) 6∈ L3 ,а 10001(100012 = 1710 = 5 × 3 + 2) ∈ L3 .4∗.
Построить ДКА, распознающий язык L3 .Задача 6. Язык L задан автоматом A. Построить минимальный автомат для языка L.bq0aq1bq2bq3aЗадача 7. Постройте минимальный автомат для языка L̄ из предыдущей задачи.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
