Sprog iterationshøjde

I teoretisk datalogi , mere præcist, i teorien om formelle sprog , er iterationshøjden et mål for den strukturelle kompleksitet af regulære udtryk - iterationshøjden af et regulært udtryk er lig med den maksimale dybde af indlejring af stjerner til stede i det regulære udtryk. udtryk. Begrebet iterationshøjde blev først introduceret og undersøgt af Eggan (1963).

Formel definition

Formelt er iterationshøjden af et regulært udtryk E over et endeligt alfabet A defineret induktivt som følger:

$\scriptstyle h\left(\emptyset \right)\,=\,0$ , og for ethvert tegn a fra alfabetet A . $\scriptstyle h\left(\varepsilon \right)\,=\,0$ $\scriptstyle h\left(a\right)\,=\,0$
$\scriptstyle h\left(EF\right)\,=\,h\left(E\,\midt \,F\right)\,=\,\max \left(\,h(E), h(F)\,\right)$
$\scriptstyle h\left(E^{*}\right)\,=\,h(E)+1.$

Her står for det tomme sæt, ε står for den tomme streng , og E og F er vilkårlige regulære udtryk. $\scriptstyle \emptyset$

Iterationshøjden h ( L ) af et regulært sprog L er defineret som minimum iterationshøjden for alle regulære udtryk, der repræsenterer L. Intuitivt, hvis et sprog L har en høj iterationshøjde, er det i sig selv komplekst, fordi det ikke kan beskrives i form af "simple" regulære udtryk med en lav iterationshøjde.

Eksempler

Selvom det er ligetil at beregne iterationshøjden for et regulært udtryk, kan definitionen af sprogets iterationshøjde nogle gange være forvirrende. Som et eksempel, det regulære udtryk

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

over alfabetet A = {a, b} har iterationshøjde 2. Det sprog, der beskrives, er dog mængden af alle ord, der ender på a . Det samme sprog kan beskrives ved hjælp af udtrykket

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

hvis iterationshøjde kun er 1. For at bevise, at et sprogs iterationshøjde er 1, skal vi udelukke muligheden for at beskrive sproget med et regulært udtryk med en lavere iterationshøjde. Det kan for eksempel gøres indirekte ved at bevise, at et sprog med iterationshøjde 0 kun indeholder et begrænset antal ord. Da vores sprog er uendeligt, kan det ikke have en iterationshøjde på 0.

Iterationshøjden for gruppesproget kan beregnes. For eksempel er højden af en sprogiteration over { a , b }, hvor antallet af forekomster af a og b er kongruente modulo 2 n , n [1] .

Eggans sætning

I sine banebrydende undersøgelser af regulære sprogs iterationshøjde etablerede Eggan [2] en forbindelse mellem teori om regulære udtryk, finite automata-teori og rettede grafer . Efterfølgende blev denne forbindelse kendt som Eggans sætning [3] . Vi husker nogle begreber fra grafteori og automatteori .

I grafteori er den cykliske rang r ( G ) af en rettet graf (digraf) G = ( V , E ) defineret induktivt som følger:

Hvis G er acyklisk , er r ( G ) = 0. Den cykliske rangorden er nul også i tilfælde af en tom graf G.
Hvis G er strengt forbundet , og E ikke er tom, så

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

hvor G - v er digrafen opnået ved at slette toppunktet v og alle buer, der starter eller slutter med v.

Hvis G ikke er strengt forbundet, så er r ( G ) lig med den maksimale cykliske rangorden blandt alle strengt forbundne komponenter i grafen G.

I automatteori defineres en ikke- deterministisk endelig automat med ε-overgange (ε-NFA) som en tupel ( Q , Σ, δ , q 0 , F ) bestående af

endeligt sæt af tilstande Q
endeligt sæt af inputsymboler Σ
sæt af mærkede buer δ , kaldet overgange : . Her betegner ε den tomme streng . $Q\times (\Sigma \cup \{\varepsilon \})\time Q$
begyndelsestilstand q 0 ∈ Q _
mængden af tilstande F , kaldet absorberende , F ⊆ Q .

Et ord w ∈ Σ * accepteres som en ε-NCF, hvis der er en orienteret kæde fra en begyndelsestilstand q 0 til en eller anden endelig tilstand F ved hjælp af digs fra δ , således at sammenkædningen af alle etiketter langs stien danner et ord w . Mængden af alle ord over Σ * accepteret af automaten er det sprog , der accepteres af automaten A .

Hvis vi taler om en ikke-deterministisk endelig automat A med et tilstandssæt Q som en rettet graf, mener vi naturligvis en graf med et vertexsæt Q genereret af overgange. Nu kan vi angive teoremet.

Eggans sætning : Iterationshøjden af et regulært sprog L er lig med den mindste cykliske rangorden blandt alle ikke- deterministiske endelige automater med ε-overgange, der accepterer sproget L.

Beviset for denne teorem blev givet af Eggan [2] , og senere af Sakarovich [3] .

Generaliseret iterationshøjdeproblem

Ovenstående definition antager, at det regulære udtryk er bygget på elementer af alfabetet A , og kun bruger standardoperationerne for sætforening , sammenkædning og Kleene-lukning . Et generaliseret regulært udtryk er defineret som et regulært udtryk , men inkluderer også en sæt komplementoperation (komplementet tages altid i forhold til alle ord over A). Hvis vi antager, at det at tage polstring ikke øger højden af iterationen, dvs

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

vi kan definere den generaliserede regulære sprogs iterationshøjde L som den minimale iterationshøjde blandt alle generaliserede regulære udtryk, der repræsenterer sproget L .

Bemærk, at mens sprog med nul (almindelig) iterationshøjde indeholder et begrænset antal ord, er der uendelige sprog med nul generaliseret iterationshøjde.

Eksempel . Almindelig udtryk

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

som vi så i eksemplet ovenfor, kan tilsvarende omskrives som et generaliseret regulært udtryk

\scriptstyle \emptyset ^{c}a

da komplementet til det tomme sæt er præcis alle ordene over alfabetet A . Således har mængden af alle ord over alfabetet A , der slutter med bogstavet a , en iterationshøjde på et, mens den generaliserede iterationshøjde er nul.

Sprog med nul iterationshøjde kaldes sprog uden stjerner . Det kan påvises, at et sprog L er et sprog uden stjerner, hvis og kun hvis dets syntaktiske monoid er aperiodisk [4] .

Se også

Sprog iteration højde problem
Generaliseret sprog iteration højde problem

Noter

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

Litteratur

Jean Berstel, Christophe Reutenauer. Ikke-kommutative rationelle serier med applikationer. - Cambridge: Cambridge University Press , 2011. - V. 137. - (Encyclopedia of Mathematics and Its Applications). - ISBN 978-0-521-19022-0 .
Rina S. Cohen. Teknikker til at etablere stjernehøjde for regulære sæt // Theory of Computing Systems . - 1971. - V. 5 , no. 2 . - S. 97-114 . — ISSN 1432-4350 . - doi : 10.1007/BF01702866 .
Rina S. Cohen, JA Brzozowski. Generelle egenskaber ved stjernehøjde ved regelmæssige begivenheder // Journal of Computer and System Sciences . - 1970. - T. 4 , no. 3 . - S. 260-280 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(70)80024-1 .
Lawrence C. Eggan. Overgangsgrafer og stjernehøjden for regelmæssige begivenheder // Michigan Mathematical Journal . - 1963. - T. 10 , no. 4 . - S. 385-397 . - doi : 10.1307/mmj/1028998975 .
Jacques Sakarovitch. Elementer i automatteori. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Arto Salomaa. Juveler af formel sprogteori. - Rockville, Maryland: Computer Science Press, 1981. - ISBN 0-914894-69-2 .
MP Schützenberger. På endelige monoider, der kun har trivielle undergrupper // Information og kontrol . - 1965. - T. 8 , no. 2 . - S. 190-194 . — ISSN 0019-9958 . - doi : 10.1016/S0019-9958(65)90108-7 .