Висота ітерації мови

У теоретичній інформатиці, а саме, теорії формальних мов, висота ітерації — це міра структурної складності регулярних виразів — висота ітерації регулярного виразу дорівнює найбільшій глибині вкладеності зірочок, наявних у регулярному виразі. Поняття висоти ітерації першим увів та вивчав Егган (1963).

Формальне визначення

Формально, висота ітерації регулярного виразу $E$ над скінченним алфавітом $A$ визначається індуктивно так:

• $h\left(\emptyset \right)\,=\,0$, $h\left(\varepsilon \right)\,=\,0$ і $h\left(a\right)\,=\,0$ для будь-якого символу $a$ з $A$.
• $h\left(EF\right)\,=\,h\left(E\,\mid \,F\right)\,=\,\max \left(\,h(E),h(F)\,\right)$
• $h\left(E^{*}\right)\,=\,h(E)+1.$

Тут $\emptyset$ позначає порожню множину, $\varepsilon$ означає порожній рядок, а $E$ і $F$ — довільні регулярні вирази.

Висота ітерації $h(L)$ регулярної мови $L$ визначається як найменша висота ітерації всіх регулярних виразів, що представляють $L$. Інтуїтивно зрозуміло, що якщо мова $L$ має високу висоту ітерації, вона сама по собі складна, її не можна описати в термінах «простих» регулярних виразів з низькою висотою ітерації.

Приклади

Хоча обчислити висоту ітерації регулярного виразу просто, визначення висоти ітерації мови іноді може видатися заплутаним. Наприклад, регулярний вираз

$\left(b\,\mid \,aa^{*}b\right)^{*}aa^{*}$

над алфавітом $A=\left\{a,b\right\}$ має висоту ітерації 2. Однак описувана мова являє собою множину всіх слів, що закінчуються на $a$. Цю ж мову можна описати за допомогою виразу

$(a\,\mid \,b)^{*}a$ ,

висота ітерації якого лише 1. Щоб довести, що висота ітерації мови дорівнює 1, потрібно виключити можливість опису мови регулярним виразом із меншою висотою ітерації. Наприклад, це можна зробити побічно, довівши, що мова з висотою ітерації 0 містить лише скінченне число слів. Оскільки наша мова нескінченна, вона не може мати висоту ітерації 0.

Висота ітерації групової мови обчислювана. Наприклад, висота ітерації мови над $\left\{a,b\right\}$, в якій число входжень $a$ і $b$ можна порівняти за модулем $2^{n}$, дорівнює $n$.

Теорема Еггана

Приклад автомата з циклічним рангом 1. Алгоритм Кліні перетворює його в регулярний вираз a^*b^*ba ((a|b)b^*a|ε)^* (a|b)b^*|a^*b^*b, що має висоту ітерації 2. За теоремою Еггана має існувати еквівалентний регулярний вираз із висотою ітерації ≤1. Фактично a^*b(b|a(a|b))^* описує ту ж мову.

У своїх основоположних дослідженнях висоти ітерації регулярних мов Егган установив зв'язок між теорією регулярних виразів, теорією скінченних автоматів та орієнтованими графами. Надалі цей зв'язок став відомим як теорема Еггана. Нагадаємо деякі поняття з теорії графів та теорії автоматів.

У теорії графів циклічний ранг $r(G)$ орієнтованого графа (орграфа) $G=(V,E)$ визначається індуктивно так:

• Якщо $G$ є ациклічним, $r(G)=0$. Циклічний ранг дорівнює нулю в разі порожнього графа $G$.
• Якщо $G$ сильно зв'язний і $E$ не порожня, то

$r(G)=1+\min _{v\in V}r(G-v),\,$ де $G-v$ — орграф, отриманий видаленням вершини $v$ і всіх дуг, що починаються або закінчуються у $v$.

• Якщо $G$ не сильно зв'язний, то $r(G)$ дорівнює найбільшому циклічному рангу серед усіх сильно зв'язних компонент графа $G$.

У теорії автоматів недетермінований скінченний автомат з ε-переходами (ε-НСА) визначається як кортеж (Q, Σ, δ, q₀, F), що складається з:

• скінченної множини станів Q,
• скінченної множини вхідних символів Σ,
• множини помічених дуг δ, званих переходами : $Q\times (\Sigma \cup \{\varepsilon \})\times Q$ (тут ε позначає порожній рядок),
• початкового стану q₀ ∈ Q,
• множини станів F, званих поглинальними, F⊆Q.

ε-НСА приймає слово w ∈ Σ^*, якщо існує орієнтований ланцюг із початкового стану q₀ до деякого кінцевого стану F, що використовує дуги з δ так що конкатенація всіх міток уздовж шляху утворює слово w. Множина всіх слів над Σ^*, які приймає автомат, є мовою, яку приймає автомат A.

Якщо говорити про недетермінований скінченний автомат A зі множиною станів Q як про орієнтований граф, ми природно маємо на увазі граф із множиною вершин Q, породженою переходами. Тепер можна сформулювати теорему.

Теорема Еггана: Висота ітерації регулярної мови L дорівнює найменшому циклічному рангу серед усіх недетермінованих скінченних автоматів з ε-переходами, що приймають мову L.

Доведення цієї теореми дав Егган, і пізніше Сакарович.

Узагальнена проблема висоти ітерації

Наведене вище визначення передбачає, що регулярний вираз будується на елементах алфавіту A, з використанням тільки стандартних операцій об'єднання множин, конкатенації та замикання Кліні. Узагальнений регулярний вираз визначається як регулярний вираз, але включає ще операцію доповнення множини (доповнення завжди береться відносно всіх слів над A). Якщо вважати, що взяття доповнення не збільшує висоти ітерації, тобто

$h\left(E^{c}\right)\,=\,h(E)$ ,

можна визначити узагальнену висоту ітерації регулярної мови L як найменшу висоту ітерації серед усіх узагальнених регулярних виразів, що представляють мову L.

Зауважимо, що у той час як мови з нульовою (звичайною) висотою ітерації містять скінченну кількість слів, існують нескінченні мови з нульовою узагальненою висотою ітерації.

Приклад. Регулярний вираз

$(a\,\mid \,b)^{*}a,$

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

$\emptyset ^{c}a$ ,

оскільки доповнення порожньої множини — це точно всі слова над алфавітом A. Таким чином, множина всіх слів над алфавітом A, що закінчуються буквою a, має висоту ітерації один, тоді як узагальнена висота ітерації дорівнює нулю.

Мови з нульовою висотою ітерації називають мовами без зірочок. Можна показати, що мова L є мовою без зірочок тоді й лише тоді, коли її синтаксичний моноїд є аперіодичним.

Див. також

• Задача висоти ітерації мови
• Узагальнена задача висоти ітерації мови

Література

• Jean Berstel, Christophe Reutenauer. Noncommutative rational series with applications. — Cambridge : Cambridge University Press, 2011. — Т. 137. — (Encyclopedia of Mathematics and Its Applications) — ISBN 978-0-521-19022-0.
• Rina S. Cohen. Techniques for establishing star height of regular sets // Theory of Computing Systems. — 1971. — Т. 5, вип. 2. — С. 97—114. — ISSN 1432-4350. — DOI:10.1007/BF01702866.
• Rina S. Cohen, J.A. Brzozowski. General properties of star height of regular events // Journal of Computer and System Sciences. — 1970. — Т. 4, вип. 3. — С. 260—280. — ISSN 0022-0000. — DOI:10.1016/S0022-0000(70)80024-1. Архівовано з джерела 5 червня 2022. Процитовано 5 червня 2022.
• Lawrence C. Eggan. Transition graphs and the star-height of regular events // Michigan Mathematical Journal. — 1963. — Т. 10, вип. 4. — С. 385—397. — DOI:10.1307/mmj/1028998975.
• Jacques Sakarovitch. Elements of automata theory. — Cambridge : Cambridge University Press, 2009. — ISBN 978-0-521-84425-3.
• Arto Salomaa. Jewels of formal language theory. — Rockville, Maryland : Computer Science Press, 1981. — ISBN 0-914894-69-2.
• M.P. Schützenberger. On finite monoids having only trivial subgroups // Information and Control. — 1965. — Т. 8, вип. 2. — С. 190—194. — ISSN 0019-9958. — DOI:10.1016/S0019-9958(65)90108-7. Архівовано з джерела 5 червня 2022. Процитовано 5 червня 2022.