1
Я пытаюсь доказать, что все NFA могут быть преобразованы в те, у которых есть одно конечное состояние, но я не уверен, как/если мне приходится иметь дело с случаем 0 конечных состояний.Имеет ли NFA конечные состояния?
Формальное определение (по википедии, я не хочу вытаскивать свою книгу), кажется, предполагает, что набор конечных состояний может быть пустым. Поэтому, если вы не можете отключить NFA (т. Е. С отключенным окончательным состоянием), похоже, вы не можете преобразовать это в NFA с конечным состоянием. В любом случае, я думаю, вы можете указать «для всех NFA с> 0 конечными состояниями», как этот вопрос здесь: http://cs.stackexchange.com/q/14555/29703. В этой заметке, cs.stackexchange, вероятно, является лучшим местом для этого вопроса. –
Поскольку пустое множество является подмножеством всех других наборов, моя книга также ничего не говорит о том, что должно быть окончательное состояние. –