Здравствуйте, Qulac, Вы писали:

Q>

Q>3. **Построение дополнения**: Постройте дополнение для ДКА, описывающего язык G2. Это делается путем инверсии принимающих и непринимающих состояний в ДКА G2.

Вот я так и подумал, что это делается через операции над минимализированными ДКА. Но с наскоку не смог придумать, как проверить, что язык, реализуемый одним ДКА, является подмножеством языка другого ДКА.

Синклер, наверное, рассчитывал, что эта задача проще задачи проверки эквиавалентности ДКА. А оказывается, сложнее.

P.S.

О! Мысля родилась.

А что, если построить третий автомат, объединяющий первые два, и все три минимизировать? Тогда если третий, объединенный, автомат сведется к какому-то из двух исходных, то тот, к которому сведется, он то ли, как раз, искомый, то ли наоборот — это надо подумать. А если не сведется, то ответ точно отрицательный.