Замкнутость регулярных языков относительно различных операций — различия между версиями
MikhailOK (обсуждение | вклад) (→Основные операции) |
MikhailOK (обсуждение | вклад) м (→Доказательство) |
||
Строка 14: | Строка 14: | ||
<ol start="4"> | <ol start="4"> | ||
<li><p> | <li><p> | ||
− | Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 | + | Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>. |
<br/> | <br/> | ||
При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.</p> | При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.</p> |
Версия 01:56, 8 октября 2010
Основные операции
Пусть
- регулярные языки над одним алфавитом . Тогда следующие языки также являются регулярными:Доказательство
Свойства 1,2,3 непосредственно следуют из определения регулярных языков.
При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки
и соответственно.
Инвертируем множество допускающих состояний: рассмотрим автомат
. Очевидно, он допускает те и только те слова, которые не допускает автомат .
При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.Следует из пунктов 1 и 4, т.к.
.
Автомат для пересечения языков можно построить явно, используя конструкцию пересечения автоматов:
, где
Прямой и обратный гомоморфизмы
Определение: |
Отображение | , сохраняющее операцию конкатенации , называется гомоморфизмом.
Гомоморфизм однозначно задается значениями на алфавите:
.Определение: |
Гомоморфизмом языка | называется язык .
Определение: |
Обратным гомоморфизмом языка | называется язык .