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

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

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

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \emptyset ^{c}a}$ ,

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

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

Див. також

• ^[en]
• ^[en]

Примітки

1. Sakarovitch, 2009, с. 342.
2. Eggan, 1963.
3. Sakarovitch, 2009.
4. Schützenberger, 1965.

Література

• Jean Berstel, Christophe Reutenauer. Noncommutative rational series with applications. — Cambridge : Cambridge University Press, 2011. — Т. 137. — (Encyclopedia of Mathematics and Its Applications) — .
• Rina S. Cohen. Techniques for establishing star height of regular sets // . — 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 // . — 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 // . — 1963. — Т. 10, вип. 4. — С. 385—397. — DOI:10.1307/mmj/1028998975.
• Jacques Sakarovitch. Elements of automata theory. — Cambridge : Cambridge University Press, 2009. — .
• Arto Salomaa. Jewels of formal language theory. — Rockville, Maryland : Computer Science Press, 1981. — .
• M.P. Schützenberger. On finite monoids having only trivial subgroups // . — 1965. — Т. 8, вип. 2. — С. 190—194. — ISSN 0019-9958. — DOI:10.1016/S0019-9958(65)90108-7. з джерела 5 червня 2022. Процитовано 5 червня 2022.