Ищу два доказательства (по конечным автоматам)

[nbyte]

Здравствуйте.
Подскажите пожалуйста кто знает, где я могу найти доказательства к следующим двум утверждениям

Цитата:

Дополнение языка конечного автомата, является тоже языком конечного автомата.

и

Цитата:

Если $\[{A_1},{A_2}\]$ являются языками конечного автомата, то $\[{A_1} \cup {A_2},{A_1} \cap {A_2}\]$ - являются тоже языки конечного автомата.

Желательно не очень большие, чтобы их можно было запомнить к экзамену.

[Maslov]

Класс языков конечных автоматов совпадает с классом регулярных множеств, поэтому Ваши два утверждения сводятся к утверждению о замкнутости класса регулярных множеств относительно операций объединения, пересечения и дополнения.

Почитать можно здесь: Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. (стр. 153)

[nbyte]

Ну не это неособо то что мне нужно. Точнее достаточно сложно для меня чтобы понять.
Может есть чтото полегче для понимания?

-- Пн фев 01, 2010 19:23:47 --

Может есть какая-нибудь книга где доходчиво объясняться, что такое

Цитата:

Дополнение языка конечного автомата.

Ато я очень плохо разбираюсь в этом деле.
Прочитал только книгу

Цитата:

Игошин Математическая логика и теория алгоритмов

но там этого негу.
Сижу с головной болью, незнаю где найти, чтобы почитать и разобратся. Нахожу только учебники достаточно сложные для понимания и трудно понимаемыми формулами, но конкретно чтобы были вот эти два доказательства утверждений я нигде не находил.

[Maslov]

nbyte в сообщении #284963 писал(а):

Может есть какая-нибудь книга где доходчиво объясняться, что такое
Цитата:
Дополнение языка конечного автомата.

Дополнение языка конечного автомата -- это множество слов над данным алфавитом, которые отвергаются (не распознаются) данным конечным автоматом.

Например, если конечный автомат над алфавитом $\{0, 1\}$ распознает непустые слова, составленные из чередующихся символов $0$ и $1$, то дополнение его языка -- это множество, содержащее пустое слово и все последовательности $0$ и $1$, в которых встречается по крайней мере одна комбинация $00$ или $11$.

[nbyte]

А так оказывается. Тогда с первым доказательством более-менее.
А как тогда со вторым утверждением, как его доказать?

[Maslov]

nbyte в сообщении #285033 писал(а):

А как тогда с вторым утверждением, как его доказать?

Если $A_1$ и $A_2$ -- регулярные множества, то $A_1 \cup A_2$ регулярно по определению регулярности.

Для доказательства регулярности пересечения регулярных множеств воспользуемся тем, что $A_1 \cap A_2 = \overline {\overline A_1 \cup \overline A_2}$
Дополнение регулярного множества регулярно, поэтому регулярны $\overline A_1$ и $\overline A_2$.
Объединение регулярных множеств регулярно, поэтому регулярно $\overline A_1 \cup \overline A_2$.
Дополнение регулярного множества регулярно, поэтому регулярно $\overline {\overline A_1 \cup \overline A_2}$
А значит множество $A_1 \cap A_2$ тоже регулярно.

[Профессор Снэйп]

Для дополнения возьмите детерминированный конечный автомат и просто поменяйте местами конечные и не конечные состояния.

Для пересечения годится конструкция "произведения автоматов". Пусть $M_1 = \langle Q_1, \Sigma, \delta_1, s_1, F_1 \rangle$ и $M_1 = \langle Q_2, \Sigma, \delta_2, s_2, F_2 \rangle$. Положим $Q = Q_1 \times Q_2$, $s = \langle s_1, s_2 \rangle$, $F = F_1 \times F_2$ и $\delta(\langle q_1, q_2 \rangle, a) = \langle \delta_1(q_1,a), \delta_2(q_2,a)\rangle$ для всех $q_1 \in Q_1$, $q_2 \in Q_2$ и $a \in \Sigma$. Тогда автомат $M = \langle Q, \Sigma, \delta, s, F \rangle$ распознаёт пересечение языков, распознаваемых автоматами $M_1$ и $M_2$.

Объединение равно дополнению к пересечению дополнений.

[nbyte]

Спасибо за помощь.
Ну теперь более менее понимаю суть.

[Zvezdochka]

Maslov в сообщении #285038 писал(а):

Дополнение регулярного множества регулярно, поэтому регулярны $\overline A_1$ и $\overline A_2$.

А определение дополнения для регулярного множества и обычного совпадает? А как вы доказали, что множество регулярно, если регулярно дополнение? Через теорему Клини? Могли бы объяснить и рекомендовать соответствующую литературу?

С уважением, Юлдуз.

[wolf.ram]

Хопкрофт, Мотвани, Ульман - Введение в теорию автоматов, языков и вычислений.