У меня есть NFA, как это:
и вопрос:
Являются ли языки эпсилон и пустой набор этой NFA?
Являются ли эпсилон и пустые языки NFA? (Недетерминированные конечные автоматы)
comment
Это Σ или ε?
- person Josh Lee schedule 24.06.2017
comment
Вы спрашиваете, принимает ли NFA пустое слово?
- person C-Otto schedule 24.06.2017
comment
На картинке это Σ. @ C-Otto Я знаю, что это не так, но вопрос немного сложный: / Потому что Σ и пустое множество по определению являются языками над каждым Σ.
- person Lucas schedule 24.06.2017
comment
Я не понимаю вашего вопроса. Не могли бы вы предоставить больше информации, добавить несколько примеров дел, связанных с вашим вопросом?
- person C-Otto schedule 24.06.2017
comment
@ C-Отто, дело в том, что у меня больше нет информации :D Вопрос из экзамена, и он больше ничего не говорит. Точный вопрос таков: и пустое множество, и эпсилон по определению являются языком над каждым алфавитом; они языки этого NFA? (под ЭТИМ я подразумеваю NFA с изображения выше). ОУ, еще кое-что - Σ = {a,b,c,d}
- person Lucas schedule 24.06.2017
comment
Я думаю, что я бы перефразировал это так: принимает ли этот NFA пустую строку? Этот NFA вообще не принимает никаких строк?
- person Josh Lee schedule 24.06.2017
comment
@JoshLee, это не так; d Но ты уверен, что это правильное перефразирование?
- person Lucas schedule 24.06.2017
Ответы (1)
Вашему автомату требуется минимум {b,a}, чтобы достичь конечного состояния. Следовательно, поскольку невозможно дойти до конца без перехода, в его языке нет пустого множества. Кроме того, поскольку нет пути от начала до конца, полностью состоящего из ε-переходов, невозможно достичь конечного состояния, используя только ε.
Так что нет, пустой набор и ε не являются частью языков этого NFA.
person
Mat
schedule
24.06.2017
Спасибо, Мэт :) Можно еще вопрос? Как бы вы преобразовали этот NFA в DFA?
- person Lucas; 24.06.2017
@ Лукас Не за что. К сожалению, это выходит за рамки вашего вопроса, если у вас возникли трудности с шагами, я предлагаю вам прочитать Это довольно хороший пример. Если вам все еще не удается, вы можете опубликовать другой вопрос.
- person Mat; 24.06.2017
