Регулярность множества и его дополнения

[Zvezdochka]

Помогите, используя теорему Клини, доказать, что множество регулярно, если и только если регулярно его дополнение. Как вводится определение дополнения регулярного множества?

[bnovikov]

"Дополнение регулярного множества" - это обычное дополнение подмножества ($A\setminus B$). Доказывать его регулярность нужно с помощью автомата или с помощью теоремы Майхилла-Нерода (распознаваемый язык является объединением классов конгруэнции конечного индекса).

[Zvezdochka]

bnovikov в сообщении #460225 писал(а):

"Дополнение регулярного множества" - это обычное дополнение подмножества ($A\setminus B$). Доказывать его регулярность нужно с помощью автомата или с помощью теоремы Майхилла-Нерода (распознаваемый язык является объединением классов конгруэнции конечного индекса).

Т.е. А - это множество всех слов алфавита, В - регулярное множество, то ($A\setminus B$) - дополнение?

Для доказательства с помощью автомата, верен ли будет этот автомат: (A,Q, {0,1}, \phi, \psi, q_0) ?

[bnovikov]

Zvezdochka в сообщении #460266 писал(а):

Для доказательства с помощью автомата, верен ли будет этот автомат: (A,Q, {0,1}, \phi, \psi, q_0) ?

Я не понимаю запись (A,Q, {0,1}, \phi, \psi, q_0).

[Zvezdochka]

bnovikov в сообщении #460302 писал(а):

Я не понимаю запись (A,Q, {0,1}, \phi, \psi, q_0).

$A$ - входной алфавит;
$Q$ - конечное множество состояний автомата;
${0, 1}$ - выходной алфавит;
$\phi $ - функция переходов;
$\psi $ - функция выходов;
$q_0 $ - начальное (стартовое) состояние автомата ($ q_0 \in Q$).

[bnovikov]

Пусть теперь $B$ - регулярное множество, т.е. распознаваемый язык (по теореме Клини!), и распознается он Вашим автоматом. Поменяйте в функции выходов 0 и 1 местами и Вы получите автомат, распознающий дополнение.