Признавая, является ли данный язык регулярным или нет

Question

L1 = {xy | x принадлежит L, а y не принадлежит L, L регулярный} Является ли L1 регулярным?a / c для меня x принадлежит L, поэтому он регулярный, но поскольку y не принадлежит L, он может быть регулярным или нет. Но ответ в том, что L1 регулярный. Как это можно показать.

Answer 1

Обычные языки закрыты при дополнении, поэтому, если L регулярно, то и "не L" тоже регулярно.

Поскольку они оба обычные, у обоих есть DFA. Позвоните в DFAs M1 и M2.

NFA для L1 может быть построен следующим образом:

1. иметь все состояния в M1 и M2
2. имеют тот же алфавит, что и M1 и M2
3. Иметь начальное состояние M1
4. Имеют принимающие состояния M2
5. Пусть функция перехода включает все переходы в M1 и M2, а также лямбда / эпсилон-переходы из состояний, принимаемых в M1, в начальное состояние в M2

Этот NFA будет читать x в M1, после чего он может недетерминированным образом перейти к M2 и прочитать y, принимая свой ввод. Он не может сделать это, пока не найдет правильное разделение х / у. Таким образом, этот NFA принимает наш язык, и поскольку любой язык, принятый NFA, является регулярным, этот язык является регулярным.