Почему дополнение обычного языка все еще остается обычным языком?

Question

Согласно моему учебнику, дополнение L1 = A * - L1 является обычным языком, если L1 является обычным языком.
Не включает ли A * также языки без контекста, контекстно-зависимые языки и рекурсивноПеречислимые языки?A * -L1 тоже будет включать их всех, не так ли?Тогда как это может быть регулярным?
Под представлением конечного автомата я понимаю, почему дополнение все еще остается обычным языком.Тем не менее, я не могу понять теорию, стоящую за этим.

Также, A * - L1 = A * дополнение пересечения (L1).Не является ли определение дополнения чем-то определенным дополнением тавтологией?Я не очень понимаю, как это может быть действительным.

Спасибо.

Answer 1

Я думаю, что вас смущает то, что когда вы говорите: «Не включает ли A* также языки, не зависящие от контекста, контекстно-зависимые языки и рекурсивно перечислимые языки?» Вы путаете A*, который набор строк , с Powerset(A*), который набор языков .

Это правда, что Powerset(A*) - {L1} является набором, содержащим «Языки без контекста, контекстно-зависимые языки и рекурсивно перечислимые языки», но на самом деле он не имеет отношения к теореме, которая просто говорит: для любого обычного языка L ( набор строк), затем язык A*-L, также набор строк , также является обычным языком.

TL; DR В вашем вопросе есть путаница между уровнями: наборы строк и наборы языков. Любые два разбиения A* на L и A*-L, в которых L является регулярным, также должны иметь A*-L регулярные. A* не содержит и не может «содержать языки», потому что это набор строк.

На ваш второй вопрос:

Также, A * - L1 = A * дополнение пересечения (L1). Не является ли определение дополнения чем-то определенным дополнением тавтологией?

Хороший вопрос. Я подозреваю, что если это представлено как определение, то это просто определение оператора -. Насколько я могу судить, это не определение «функции дополнения». Возможно, «дополнение» уже определено, и ваша книга сейчас пытается определить оператор вычитания. Или это скорее теорема, чем определение.

Answer 2

Я не могу найти свою копию Hopcroft & Ullman , но я думаю, что нашел правильное определение для дополнения обычного языка здесь . кажется правильным и более понятным для разговора, чтобы сказать, что дополнением L является DFA, который принимает любую строку , за исключением тех, которые являются членами L. Таким образом, вы перемещаете состояние принятия всем (ранее) непринятие состояний и все готово. Поскольку комплемент - это просто перестановка DFA, результатом по-прежнему остается DFA.

Что касается записи, я думаю, что вы читаете ее как L1 = A* - L1, когда она должна быть правильно прочитана как complement L1 = A* - L1, где complement - оператор дополнения.

Answer 3

Если вы можете понять автоматное доказательство, тогда у вас есть все. Интуиция заключается в том, что если вы можете распознать обычный язык, запустив автомат и увидев, останавливается ли он в конечном состоянии, то вы можете распознать дополнение этого языка (по набору всех строк), просто запустив тот же автомат и видеть, останавливается ли на не финальном состоянии. Поскольку все строки останавливаются в некотором состоянии, а язык является регулярным тогда и только тогда, когда он останавливается в конечном состоянии, он нерегулярен тогда и только тогда, когда он останавливается в неконечном состоянии. Я думаю, это довольно интуитивно понятно. Кроме того, единственное, что вам нужно доказать себе, что язык является регулярным, - это построить для него автомат: просто поменяйте местами все конечные и не конечные состояния.