Закрытие на обычных языках

Question

А) Пусть $L$ будьте обычным языком.согласно теореме, существует DFA, который принимает этот язык.

Кратко опишите, как изменить DFA на NFA, который принимает $L^R$, где R - обратное значение.

Нет необходимости писать, как построить формальное доказательство или корректность.

Б) Истина или Ложь:если $L$ значит, это нерегулярно $L^R$ не является регулярным

Мое решение:

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

Б) Я думаю, что это правда, так как не имеет значения, перевернуто ли оно, если оно обычное, тогда, конечно $L^R$ также будет регулярным.

Подходит ли это для A и B?

Answer 1

А)

Прежде всего, поскольку мы хотим обратного, чтобы принимающее состояние стало началом, а отклоняющие состояния стали принимающими, также измените направление краев на противоположную сторону.

Ты почти на месте.Что произойдет, если у вас есть несколько принимающих состояний в исходном DFA?Вот где вам понадобятся возможности NFA для их преобразования.

Вот спойлер на случай, если вы захотите проверить свой ответ: Проектирование DFA и обратная сторона его на ComputerScience.SE.

Б)

Ваш ответ верен, хотя вы, возможно, захотите сформулировать его немного более аккуратно.Мы хотим доказать , "если $L$ не является регулярным, $L^R$ не является регулярным".Так что пусть $L$ будьте нерегулярны.Если $L^R$ были регулярными, так что были $(L^ R)^R = L$, что является противоречием.Следовательно, $L^R$ не является регулярным.