Написать на с++

[hanter (арман)]

а) Построить ДКА (детерминированный конечный автомат), допускающий в алфавите {0, 1} все цепочки
нулей и единиц, в которых символ 1 следует непосредственно за парой 00.
Пример 1: Цепочки 101, 0010, 0010011001 принадлежат языку. Пример 2:
цепочки 0001 и 00100 — не принадлежат.
б) Построить НКА (недетерминированный конечный автомат), допускающий цепочки в алфавите Z = {0, 1}, в которых
содержится два нуля, разделенных позициями в количестве, кратном 4.
Примечание: нуль тоже кратен 4.

[Двойкин]

sed -E "s/^((1|01|001)*0?)$/\1-подходит/g"<<EOF
101
0010
0010011001
0001
00100
EOF

sed -E "s/^(.*0((0|1)(0|1)(0|1)(0|1))?0.*)$/\1-подходит/g"<<EOF
101
0010
0010011001
0001
00100
EOF

Это, конечно, не C++ (sed написан на C и было это 49 лет назад), но задачу почти решает… Почти, потому что во втором случае не НКА.

[Двойкин]

Убирание ε-переходов (а так же поиск ошибок) оставляется читателю в качестве упражнения: