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

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

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

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

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

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

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

• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл/CRC. ISBN 1-58488-255-7. Збл  1086.68074.
• Diekert, Volker; Gastin, Paul (2008). "First-order definible languages". В Jörg Flum; Erich Grädel; Thomas Wilke (ред.). Logic and automata: history and perspectives (PDF) . Amsterdam University Press. ISBN 978-90-5356-576-6.