(Объяснение и объяснение) NFA принимает пустую строку тогда и только тогда, когда ее начальное состояние является конечным

Question

Принимает ли NFA пустую строку тогда и только тогда, когда ее начальное состояние является конечным?Это правда?

Пожалуйста, объясните, почему.

Этот вопрос относится к автоматам, NFA и DFA.

Answer 1

Это неверно.Рассмотрим NFA с двумя состояниями с неприемлемым начальным состоянием, ведущим к принимающему состоянию посредством лямбда- (или эпсилон-, или пустого) перехода.Пустая строка принимается этим NFA при прохождении перехода, но исходное состояние неприемлемо.

Если бы утверждение касалось DFA, то это было бы верно, поскольку lambda- (или epsilon-, илипусто) переходы будут недоступны.