Пересечение и объединение регулярного и нерегулярного языка

12

Пусть регулярный, регулярный, не регулярный. Покажите, что не является регулярным, или приведите контрпример.L1L1L2L2L1L2

Я попробовал это: Посмотрите на . Это регулярно. Для этого я могу построить конечный автомат: регулярный, регулярный, поэтому удалите все пути (конечное количество) для из конечного количества путей для . Таким образом, для всего этого есть ограниченное количество путей. Эта вещь не пересекается с , но как я могу доказать, что объединение (регулярное) и (не регулярное) не является регулярным?L1(L2L1)L1L2L1L1L2L1L2L1(L1L2)L2

Kevin
источник
«Итак, удалите все пути (конечное количество) для из конечного количества путей для » - что это должно означать? Обычным способом построения автомата для разности является использование и хорошо известных конструкций для дополнения и пересечения. L1L2L1AB=AB¯
Рафаэль
Я предпочитаю менять название этого вопроса. Название вопроса само по себе является неправильным.
Нитищ

Ответы:

19

Мы можем доказать это противоречием. Давайте определим . Тогда мы можем переформулировать :L1¯=ΣL1L2

L2=((L1L2)L1)(L1L2)=((L1L2)L1¯)(L1L2)

Мы знаем:

  • Обычные языки закрыты на объединение, пересечение и дополнение
  • L1¯ и являются регулярнымиL1L2
  • L2 не регулярно

Теперь предположим, что является регулярным: Тогда является регулярным (так как это только объединение / пересечение регулярных языков), поэтому будет обычным. Это противоречие, поэтому наше предположение неверно, и не может быть регулярным.L1L2((L1L2)L1¯)(L1L2)L2L1L2

Майк Б.
источник
Я думаю, что понял. Но почему дополнение обычного языка регулярно? Я не понимаю эту часть.
Кевин
1
@Kevin Это известная лемма, поэтому вы должны найти доказательство в любом учебнике. Один из способов доказательства - взять конечный автомат и поменять принимающее и непринятое состояния: вы получаете автомат, который распознает язык дополнения.
Жиль "ТАК - перестать быть злым"
А что за недетерминированные конечные автоматы? Предположим, у нас есть автоматы. , одно начальное состояние, две стрелки из этого состояния с в другое состояние. Одно из этих состояний принимает, а другое нет. Итак, . Если мы теперь поменяем принимающие состояния, он все равно будет принимать , поэтому он не считает, что он принимает язык дополнения! A={a,b}aL(M)={a}{a}
Кевин
Доказательство Жиля работает только для детерминированных конечных автоматов, что - для обычных языков - не является ограничением. Но, по его словам, эту лемму можно найти в любом учебнике.
Майк Б.
1
@Kevin: Майк означает, что у каждого обычного языка есть детерминированный автомат, который распознает его, поэтому вы всегда можете его использовать.
reinierpost
-4

Это не правильно. Рассмотрим , . регулярный, нет; но .L1={a,b}L2={anbn:n0}L1L2L1L2=L1

vonbrand
источник
5
Вы не выполнили условие, что является регулярным. L1L2
Андрей Бауэр