Kieliiteroinnin korkeus

Teoreettisessa tietojenkäsittelytieteessä , tarkemmin sanottuna muodollisten kielten teoriassa , iterointikorkeus on säännöllisten lausekkeiden rakenteellisen monimutkaisuuden mitta - säännöllisen lausekkeen iteraatiokorkeus on yhtä suuri kuin säännöllisessä lausekkeessa olevien tähtien sisäkkäisyyden maksimi syvyys. ilmaisu. Iteraatiokorkeuden käsitteen esitteli ja tutki ensimmäisenä Eggan (1963).

Muodollinen määritelmä

Muodollisesti säännöllisen lausekkeen E iteraatiokorkeus äärellisen aakkoston A yli määritellään induktiivisesti seuraavasti:

$\scriptstyle h\left(\emptyset \right)\,=\,0$ , ja mille tahansa merkille a aakkosesta A . $\scriptstyle h\left(\varepsilon \right)\,=\,0$ $\scriptstyle h\left(a\right)\,=\,0$
$\scriptstyle h\left(EF\oikea)\,=\,h\left(E\,\mid \,F\oikea)\,=\,\max \left(\,h(E), h(F)\,\oikea)$
$\scriptstyle h\left(E^{*}\right)\,=\,h(E)+1.$

Tässä tarkoittaa tyhjää joukkoa, ε tarkoittaa tyhjää merkkijonoa ja E ja F ovat mielivaltaisia säännöllisiä lausekkeita. $\scriptstyle \emptyset$

Säännöllisen kielen L iteraatiokorkeus h ( L ) määritellään kaikkien L: tä edustavien säännöllisten lausekkeiden vähimmäisiteraatiokorkeudeksi . Intuitiivisesti, jos kielellä L on korkea iteraatiokorkeus, se on itsessään monimutkainen, koska sitä ei voida kuvata "yksinkertaisilla" säännöllisillä lausekkeilla, joilla on pieni iteraatiokorkeus.

Esimerkkejä

Vaikka säännöllisen lausekkeen iteraatiokorkeuden laskeminen on yksinkertaista, kielen iteraatiokorkeuden määrittely voi joskus olla hämmentävää. Esimerkkinä säännöllinen lauseke

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

aakkosten A = {a, b} iteraatiokorkeus on 2. Kuvattava kieli on kuitenkin joukko kaikkia a -päätteisiä sanoja . Samaa kieltä voidaan kuvata käyttämällä lauseketta

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

jonka iteraatiokorkeus on vain 1. Osoittaaksemme, että kielen iteraatiokorkeus on 1, meidän on suljettava pois mahdollisuus kuvata kieli säännöllisellä lausekkeella, jonka iterointikorkeus on pienempi. Tämä voidaan tehdä esimerkiksi epäsuorasti todistamalla, että kieli, jonka iterointikorkeus on 0, sisältää vain äärellisen määrän sanoja. Koska kielemme on ääretön, sen iteraatiokorkeus ei voi olla 0.

Ryhmäkielen iteraatiokorkeus on laskettavissa. Esimerkiksi kielten iteraation korkeus { a , b }:n yli, jossa a :n ja b :n esiintymien lukumäärä on yhteneväinen modulo 2 n , on n [1] .

Egganin lause

Säännöllisten kielten iteraatiokorkeutta koskevissa keskeisissä tutkimuksissaan Eggan [2] loi yhteyden säännöllisten lausekkeiden teorian, äärellisten automaattien teorian ja suunnattujen graafien välille . Myöhemmin tämä yhteys tuli tunnetuksi Egganin lauseena [3] . Muistamme joitain käsitteitä graafiteoriasta ja automaatiteoriasta .

Graafiteoriassa suunnatun graafin (digraafin) syklinen arvo r ( G ) G = ( V , E ) määritellään induktiivisesti seuraavasti:

Jos G on asyklinen , r ( G ) = 0. Jakso on nolla myös tyhjän graafin G tapauksessa.
Jos G on tiukasti kytketty ja E ei ole tyhjä, niin

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

jossa G - v on digraafi, joka saadaan poistamalla kärki v ja kaikki kaaret, jotka alkavat tai päättyvät v:llä.

Jos G ei ole tiukasti kytketty, niin r ( G ) on yhtä suuri kuin graafin G kaikkien tiukasti kytkettyjen komponenttien syklinen maksimiarvo.

Automaattiteoriassa epädeterministinen äärellinen automaatti ε-siirtymällä (ε-NFA) määritellään monikkona ( Q , Σ , δ , q 0 , F ), joka koostuu

äärellinen joukko tiloja Q
äärellinen joukko syöttösymboleja Σ
sarjaa merkittyjä kaaria δ , joita kutsutaan siirtymäksi : . Tässä ε tarkoittaa tyhjää merkkijonoa . $Q\times (\Sigma \cup \{\varepsilon \})\times Q$
alkutila q 0 ∈ Q _
tilojen joukko F , jota kutsutaan absorboivaksi , F ⊆ Q .

Sana w ∈ Σ * hyväksytään ε-NCF:ksi, jos on suuntautunut ketju alkutilasta q 0 johonkin lopputilaan F käyttämällä digs arvosta δ siten, että kaikkien polun varrella olevien nimikkeiden ketjutus muodostaa sanan w . Kaikkien Σ * :n yli olevien sanojen joukko, jonka automaatti hyväksyy, on automaatin A hyväksymä kieli .

Jos puhutaan epädeterministisesta äärellisestä automaatista A , jonka tilajoukko Q on suunnattu graafina, tarkoitamme luonnollisesti graafia, jonka kärkijoukko Q on generoitu siirtymillä. Nyt voimme esittää lauseen.

Egganin lause : Säännöllisen kielen L iteraatiokorkeus on yhtä suuri kuin pienin syklinen arvo kaikkien epädeterminististen äärellisten automaattien joukossa , joiden ε-siirtymät hyväksyvät kielen L.

Tämän lauseen todistuksen antoi Eggan [2] ja myöhemmin Sakarovich [3] .

Yleistetty iteroinnin korkeusongelma

Yllä oleva määritelmä olettaa, että säännöllinen lauseke on rakennettu aakkosten A elementteihin käyttäen vain joukkoliiton , ketjutuksen ja Kleenen sulkemisen vakiooperaatioita . Yleistetty säännöllinen lauseke määritellään säännölliseksi lausekkeeksi, mutta se sisältää myös joukkokomplementtioperaation ( komplementti otetaan aina suhteessa kaikkiin A:n sanoihin). Jos oletetaan, että täytteen ottaminen ei lisää iteroinnin korkeutta, se on

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

voimme määritellä yleistetyn säännöllisen kielen iteraatiokorkeuden L vähimmäisiteraatiokorkeudeksi kaikkien kieltä L edustavien yleistettyjen säännöllisten lausekkeiden joukossa .

Huomaa, että vaikka kielet, joilla on nolla (tavallinen) iteraatiokorkeus, sisältävät äärellisen määrän sanoja, on ääretön kieliä, joilla on nolla yleinen iteraatiokorkeus.

Esimerkki . Tavallinen ilme

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

jonka näimme yllä olevassa esimerkissä, voidaan vastaavasti kirjoittaa uudelleen yleistetyksi säännölliseksi lausekkeeksi

\scriptstyle \emptyset ^{c}a

koska tyhjän joukon komplementti on täsmälleen kaikki aakkosten A sanat . Siten kaikkien aakkosten A ylittävien sanojen joukon, joka päättyy kirjaimeen a , iteraatiokorkeus on yksi, kun taas yleisen iteroinnin korkeus on nolla.

Kieliä, joiden iteraatiokorkeus on nolla, kutsutaan kieliksi ilman tähtiä . Voidaan osoittaa, että kieli L on kieli ilman tähtiä silloin ja vain, jos sen syntaktinen monoidi on ajaksoinen [4] .

Katso myös

Kieliiteroinnin korkeusongelma
Yleistetty kielen iteroinnin korkeusongelma

Muistiinpanot

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

Kirjallisuus

Jean Berstel, Christophe Reutenauer. Ei-kommutatiiviset rationaaliset sarjat sovelluksilla. - Cambridge: Cambridge University Press , 2011. - V. 137. - (Encyclopedia of Mathematics and Its Applications). - ISBN 978-0-521-19022-0 .
Rina S. Cohen. Tekniikat säännöllisten joukkojen tähtien korkeuden määrittämiseksi // Tietojenkäsittelyjärjestelmien teoria . - 1971. - V. 5 , no. 2 . - S. 97-114 . — ISSN 1432-4350 . - doi : 10.1007/BF01702866 .
Rina S. Cohen, JA Brzozowski. Säännöllisten tapahtumien tähtikorkeuden yleiset ominaisuudet // 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. Siirtymäkaaviot ja säännöllisten tapahtumien tähtien korkeus // Michigan Mathematical Journal . - 1963. - T. 10 , no. 4 . - S. 385-397 . - doi : 10.1307/mmj/1028998975 .
Jacques Sakarovitch. Automaattiteorian elementit. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Arto Salomaa. Formaalin kieliteorian jalokiviä. - Rockville, Maryland: Computer Science Press, 1981. - ISBN 0-914894-69-2 .
kansanedustaja Schützenberger. Äärillisillä monoideilla, joilla on vain triviaaleja alaryhmiä // Informaatio ja ohjaus . - 1965. - T. 8 , no. 2 . - S. 190-194 . — ISSN 0019-9958 . - doi : 10.1016/S0019-9958(65)90108-7 .