Пусть регулярный, регулярный, не регулярный. Покажите, что не является регулярным, или приведите контрпример.
Я попробовал это: Посмотрите на . Это регулярно. Для этого я могу построить конечный автомат: регулярный, регулярный, поэтому удалите все пути (конечное количество) для из конечного количества путей для . Таким образом, для всего этого есть ограниченное количество путей. Эта вещь не пересекается с , но как я могу доказать, что объединение (регулярное) и (не регулярное) не является регулярным?
Ответы:
Мы можем доказать это противоречием. Давайте определим . Тогда мы можем переформулировать :L1¯¯¯¯¯¯=Σ∗∖L1 L2
Мы знаем:
Теперь предположим, что является регулярным: Тогда является регулярным (так как это только объединение / пересечение регулярных языков), поэтому будет обычным. Это противоречие, поэтому наше предположение неверно, и не может быть регулярным.L1∪L2 ((L1∪L2)∩L1¯¯¯¯¯¯)∪(L1∩L2) L2 L1∪L2
источник
Это не правильно. Рассмотрим , . регулярный, нет; но .L1={a,b}∗ L2={anbn:n≥0} L1 L2 L1∪L2=L1
источник