Înălțimea iterației limbajului

În informatica teoretică , mai precis, în teoria limbajelor formale , înălțimea iterației este o măsură a complexității structurale a expresiilor regulate - înălțimea iterației unei expresii regulate este egală cu adâncimea maximă de imbricare a asteriscurilor prezente în expresiile regulate. expresie. Conceptul de înălțime de iterație a fost introdus și studiat pentru prima dată de Eggan (1963).

Definiție formală

Formal, înălțimea de iterație a unei expresii regulate E peste un alfabet finit A este definită inductiv după cum urmează:

$\scriptstyle h\left(\emptyset \right)\,=\,0$ , iar pentru orice caracter a din alfabetul A . $\scriptstyle h\left(\varepsilon \right)\,=\,0$ $\scriptstyle h\stanga(a\dreapta)\,=\,0$
$\scriptstyle h\left(EF\right)\,=\,h\left(E\,\mid \,F\right)\,=\,\max \left(\,h(E), h(F)\,\dreapta)$
$\scriptstyle h\left(E^{*}\right)\,=\,h(E)+1.$

Aici reprezintă mulțimea goală, ε reprezintă șirul gol , iar E și F sunt expresii regulate arbitrare. $\scriptstyle \emptyset$

Înălțimea de iterație h ( L ) a unui limbaj regulat L este definită ca înălțimea minimă de iterație a tuturor expresiilor regulate care reprezintă L . Intuitiv, dacă un limbaj L are o înălțime mare de iterație, ea însăși este complexă deoarece nu poate fi descrisă în termeni de expresii regulate „simple” cu o înălțime de iterație mică.

Exemple

În timp ce calcularea înălțimii de iterație a unei expresii regulate este simplă, definiția înălțimii de iterație a limbajului poate fi uneori confuză. De exemplu, expresia regulată

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

peste alfabetul A = {a, b} are înălțimea iterației 2. Cu toate acestea, limbajul descris este setul tuturor cuvintelor care se termină cu a . Același limbaj poate fi descris folosind expresia

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

a căror înălțime de iterație este doar 1. Pentru a demonstra că înălțimea de iterație a unei limbi este 1, trebuie să excludem posibilitatea de a descrie limbajul printr-o expresie regulată cu o înălțime de iterație mai mică. De exemplu, acest lucru se poate face indirect prin demonstrarea că o limbă cu înălțimea iterației 0 conține doar un număr finit de cuvinte. Deoarece limba noastră este infinită, nu poate avea o înălțime de iterație de 0.

Înălțimea de iterație a limbajului de grup este calculabilă. De exemplu, înălțimea unei iterații de limbaj peste { a , b } în care numărul de apariții ale lui a și b sunt congruente modulo 2 n este n [1] .

Teorema lui Eggan

În studiile sale fundamentale privind înălțimea iterației limbajelor regulate, Eggan [2] a stabilit o legătură între teoria expresiilor regulate, teoria automatelor finite și graficele direcționate . Ulterior, această conexiune a devenit cunoscută sub numele de teorema lui Eggan [3] . Reamintim câteva concepte din teoria grafurilor și teoria automatelor .

În teoria grafurilor, rangul ciclic r ( G ) al unui graf direcționat (digraf) G = ( V , E ) este definit inductiv după cum urmează:

Dacă G este aciclic , r ( G ) = 0. Rangul ciclic este zero și în cazul unui grafic G gol.
Dacă G este strict conectat și E nu este gol, atunci

r(G)=1+\min _{v\in V}r(Gv),\,

unde G - v este digraful obținut prin ștergerea vârfului v și a tuturor arcelor care încep sau se termină cu v.

Dacă G nu este strict conectat, atunci r ( G ) este egal cu rangul ciclic maxim dintre toate componentele strict conectate ale graficului G.

În teoria automatelor , un automat finit nedeterminist cu ε-tranziții (ε-NFA) este definit ca un tuplu ( Q , Σ, δ , q 0 , F ) format din

set finit de stări Q
set finit de simboluri de intrare Σ
seturi de arce etichetate δ , numite tranziții : . Aici ε desemnează șirul gol . $Q\times (\Sigma \cup \{\varepsilon \})\times Q$
starea initiala q 0 ∈ Q
mulţimea stărilor F , numită absorbantă , F ⊆ Q .

Un cuvânt w ∈ Σ * este acceptat ca ε-NCF dacă există un lanț orientat de la o stare inițială q 0 la o stare finală F folosind săpături din δ astfel încât concatenarea tuturor etichetelor de-a lungul căii să formeze un cuvânt w . Mulțimea tuturor cuvintelor peste Σ * acceptate de automat este limbajul acceptat de automatul A .

Dacă vorbim despre un automat finit nedeterminist A cu o mulțime de stări Q ca graf direcționat, ne referim în mod natural la un graf cu o mulțime de vârfuri Q generată de tranziții. Acum putem afirma teorema.

Teorema lui Eggan : Înălțimea de iterație a unui limbaj regulat L este egală cu cel mai mic rang ciclic dintre toate automatele finite nedeterministe cu ε-tranziții care acceptă limbajul L.

Dovada acestei teoreme a fost dată de Eggan [2] , iar mai târziu de Sakarovich [3] .

Problemă generalizată a înălțimii iterației

Definiția de mai sus presupune că expresia regulată este construită pe elemente ale alfabetului A , folosind doar operațiile standard de unire a seturilor , concatenare și închidere Kleene . O expresie regulată generalizată este definită ca o expresie regulată, dar include și o operație de complement de set (complementul este întotdeauna luat în raport cu toate cuvintele de peste A). Dacă presupunem că luarea de umplutură nu crește înălțimea iterației, adică

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

putem defini înălțimea generalizată a iterației limbajului regulat L ca înălțimea minimă a iterației dintre toate expresiile regulate generalizate care reprezintă limbajul L .

Rețineți că, în timp ce limbile cu înălțime de iterație zero (obișnuită) conțin un număr finit de cuvinte, există limbi infinite cu înălțime de iterație generalizată zero.

Exemplu . Expresie uzuala

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

ceea ce am văzut în exemplul de mai sus poate fi rescris în mod echivalent ca expresie regulată generalizată

\scriptstyle \emptyset ^{c}a

întrucât complementul mulţimii goale este exact toate cuvintele de peste alfabetul A . Astfel, setul tuturor cuvintelor de pe alfabetul A care se termină cu litera a are o înălțime de iterație de unu, în timp ce înălțimea de iterație generalizată este zero.

Limbile cu înălțime de iterație zero sunt numite limbi fără asteriscuri . Se poate arăta că o limbă L este o limbă fără asteriscuri dacă și numai dacă monoidul său sintactic este aperiodic [4] .

Vezi și

Problemă de înălțime a iterației limbajului
Problemă generalizată a înălțimii iterației limbajului

Note

↑ Sakarovici, 2009 , p. 342.
↑ 12 Eggan , 1963 .
↑ 12 Sakarovitch , 2009 .
↑ Schützenberger, 1965 .

Literatură

Jean Berstel, Christophe Reutenauer. Serii raționale necomutative cu aplicații. - Cambridge: Cambridge University Press , 2011. - V. 137. - (Encyclopedia of Mathematics and Its Applications). - ISBN 978-0-521-19022-0 .
Rina S. Cohen. Tehnici de stabilire a înălțimii stelelor a mulțimilor regulate // Teoria sistemelor de calcul . - 1971. - V. 5 , nr. 2 . - S. 97-114 . — ISSN 1432-4350 . - doi : 10.1007/BF01702866 .
Rina S. Cohen, JA Brzozowski. Proprietăți generale ale înălțimii stelei a evenimentelor regulate // Journal of Computer and System Sciences . - 1970. - T. 4 , nr. 3 . - S. 260-280 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(70)80024-1 .
Lawrence C. Eggan. Grafice de tranziție și înălțimea stelei a evenimentelor regulate // Michigan Mathematical Journal . - 1963. - T. 10 , nr. 4 . - S. 385-397 . - doi : 10.1307/mmj/1028998975 .
Jacques Sakarovitch. Elemente de teoria automatelor. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Arto Salomaa. Bijuterii teoriei limbajului formal. - Rockville, Maryland: Computer Science Press, 1981. - ISBN 0-914894-69-2 .
deputatul Schützenberger. Pe monoizi finiți având doar subgrupuri triviale // Informație și control . - 1965. - T. 8 , nr. 2 . - S. 190-194 . — ISSN 0019-9958 . - doi : 10.1016/S0019-9958(65)90108-7 .