Почему дополнение к регулярному языку по-прежнему остается регулярным языком?

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

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

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

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

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

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

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

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