Язык без звезд

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

Например, язык $\Sigma ^{*}$ всех конечных слов в алфавите $\Sigma$ можно показать, что он свободен от звезд, взяв дополнение к пустому множеству, $\Sigma ^{*}={\bar {\emptyset }}$. Тогда язык слов над алфавитом $\{a,\,b\}$ которые не имеют последовательных букв, могут быть определены как ${\overline {\Sigma ^{*}aa\Sigma ^{*}}}$, сначала построив язык слов, состоящий из $aa$ с произвольным префиксом и суффиксом, а затем беря его дополнение, которым должны быть все слова, не содержащие подстроку $aa$.

Пример регулярного языка, который не свободен от звезд: $(aa)^{*}$, т.е. язык строк, состоящий из четного числа «а». Для $(ab)^{*}$ где $a\neq b$, язык можно определить как $\Sigma ^{*}\setminus (b\Sigma ^{*}\cup \Sigma ^{*}a\cup \Sigma ^{*}aa\Sigma ^{*}\cup \Sigma ^{*}bb\Sigma ^{*})$, взяв набор всех слов и удалив из него слова, начинающиеся с $b$, заканчивающийся на $a$ или содержащий $aa$ или $bb$. Однако, когда $a=b$, это определение не создает $(aa)^{*}$.

Марсель-Поль Шютценбергер охарактеризовал беззвездные языки как языки с апериодическими синтаксическими моноидами . Их также можно логически охарактеризовать как языки, определяемые в FO[<), логике первого порядка над натуральными числами с отношением «меньше», как языки, свободные от счетчиков и как языки, определяемые в линейной темпоральной логике .

Все беззвездные языки находятся в едином AC. ⁰ .

См. также

• Высота звезды
• Проблема с высотой звезды
• Обобщенная проблема высоты звезды

Ссылки

• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл/CRC. ISBN  1-58488-255-7 . Збл   1086.68074 .
• Дикерт, Волкер; Гастин, Пол (2008). «Определимые языки первого порядка». В Йорге Флуме; Эрих Гредель; Томас Уилк (ред.). Логика и автоматы: история и перспективы (PDF) . Издательство Амстердамского университета. ISBN  978-90-5356-576-6 .