задача по теории автоматов

kiptilyy2009

Написать схему НА, который аннулирует входное слово тогда и только тогда, когда оно содержит не менее трех вхождений некоторого фиксированного непустого слова u.
подскажите как делать

Dina

Не совсем понятно, что значит аннулирует? Если речь о том, что он распознает такие слова, то надо стандартным образом построить автомат по регулярному выражению:
{0,1}^* u {0,1}^* u {0,1}^* u {0,1}^*.

stm8853410

Если вхождения слова u могут перекрываться (например, в слове 000000 есть три вхождения слова 0000 то нужно сложнее.
Сначала строим A — автомат Ахо-Корасик для слова u.
Новый автомат будет состоять из трёх слоёв, каждый из которых выглядит как А. При этом из терминальной вершины первого слоя идут рёбра во второй слой, из терминальной вершины второго слоя ведут рёбра в третий слой, а терминальная вершина третьего слоя будет терминальной вершиной всего нового автомата. Как-то так.
Оставить комментарий
Имя или ник:
Комментарий: