Nyelvi iteráció magassága

Az elméleti számítástechnikában , pontosabban a formális nyelvek elméletében az iterációs magasság a reguláris kifejezések  szerkezeti összetettségének mértéke  - egy reguláris kifejezés iterációs magassága megegyezik a reguláris kifejezésben található csillagok egymásba ágyazási mélységével. kifejezés. Az iterációs magasság fogalmát először Eggan vezette be és tanulmányozta (1963).

Formális definíció

Formálisan egy E reguláris kifejezés iterációs magassága egy véges A ábécé felett induktív módon a következőképpen definiálható:

Itt az üres halmazt, az ε az üres karakterláncot jelöli, az E és F pedig  tetszőleges reguláris kifejezések.

Egy L reguláris nyelv h ( L ) iterációs magassága az L -t képviselő összes reguláris kifejezés minimális iterációs magassága . Intuitív módon, ha egy L nyelvnek nagy az iterációs magassága, akkor maga is összetett, mert nem írható le alacsony iterációs magasságú "egyszerű" reguláris kifejezésekkel.

Példák

Míg egy reguláris kifejezés iterációs magasságának kiszámítása egyszerű, a nyelv iterációs magasságának meghatározása néha zavaró lehet. Példaként a reguláris kifejezés

Az A = {a, b} ábécé fölött 2 iterációs magasságú. A leírt nyelv azonban az összes a-ra végződő szó halmaza . Ugyanez a nyelv leírható a kifejezés segítségével

,

amelynek iterációs magassága csak 1. Annak bizonyításához, hogy egy nyelv iterációs magassága 1, ki kell zárnunk annak lehetőségét, hogy a nyelvet kisebb iterációs magasságú reguláris kifejezéssel írjuk le. Ez például közvetve megtehető, ha bebizonyítjuk, hogy egy 0 iterációs magasságú nyelv csak véges számú szót tartalmaz. Mivel nyelvünk végtelen, nem lehet 0 iterációs magassága.

A csoportnyelv iterációs magassága kiszámítható. Például egy olyan nyelvi iteráció magassága { a , b } felett, amelyben a és b előfordulások száma egybevágó modulo 2 n n [ 1 ] .

Eggan tétele

A reguláris nyelvek iterációs magasságával foglalkozó alapvető tanulmányaiban Eggan [2] kapcsolatot teremtett a reguláris kifejezés elmélete, a véges automata elmélet és az irányított gráfok között . Később ez az összefüggés Eggan tételeként vált ismertté [3] . Felidézünk néhány fogalmat a gráfelméletből és az automataelméletből .

A gráfelméletben egy irányított gráf (digráf) G  = ( V ,  E ) ciklikus rangját r ( G ) induktív módon a következőképpen definiáljuk:

 ahol G - v a v csúcs és az összes v-vel kezdődő vagy végződő ív törlésével kapott digráf.

Az automataelméletben egy nem determinisztikus véges automatát ε-átmenetekkel (ε-NFA) úgy definiálunk, mint egy sor ( Q , Σ, δ , q 0 , F ), amely a következőkből áll.

Egy w ∈ Σ * szót akkor fogadunk el ε-NCF-nek, ha van egy orientált lánc egy q 0 kezdeti állapottól valamilyen F végállapotig , δ -ből való digs segítségével úgy, hogy az útvonal mentén lévő összes címke összefűzése w szót képez . Az automata által elfogadott Σ * feletti összes szó halmaza az A automata által elfogadott nyelv .

Ha egy Q állapothalmazú nemdeterminisztikus A véges automatáról beszélünk irányított gráfként, akkor természetesen átmenetek által generált Q csúcshalmazú gráfot értünk . Most kijelenthetjük a tételt.

Eggan tétel : Egy L reguláris nyelv iterációs magassága egyenlő az L nyelvet elfogadó ε-átmenetekkel rendelkező összes nemdeterminisztikus véges automata legkisebb ciklikus rangjával .

Ennek a tételnek a bizonyítását Eggan [2] , majd később Sakarovich [3] adta meg .

Általános iterációs magasság probléma

A fenti definíció feltételezi, hogy a reguláris kifejezés az A ábécé elemeire épül , és csak a halmazegyesítés , az összefűzés és a Kleene-zárás szabványos műveleteit használja . Az általánosított reguláris kifejezés reguláris kifejezésként van definiálva, de tartalmaz egy halmazkomplementműveletet is (a kiegészítést mindig az A-n keresztüli összes szóhoz viszonyítva veszik fel). Ha feltételezzük, hogy a kitöltés nem növeli az iteráció magasságát, akkor az

,

meghatározhatjuk az L általánosított reguláris nyelvi iterációs magasságot , mint a minimális iterációs magasságot az L nyelvet reprezentáló összes általánosított reguláris kifejezés között .

Vegye figyelembe, hogy míg a nulla (közönséges) iterációs magasságú nyelvek véges számú szót tartalmaznak, vannak végtelen nyelvek nulla általánosított iterációs magassággal.

Példa . Reguláris kifejezés

amelyet a fenti példában láttunk, egyenértékűen átírhatjuk általánosított reguláris kifejezésként

,

mivel az üres halmaz kiegészítése pontosan az A ábécé feletti összes szó . Így az A ábécé feletti összes szó halmaza, amely a betűvel végződik, iterációs magassága egy , míg az általánosított iterációs magasság nulla.

A nulla iterációs magasságú nyelveket csillag nélküli nyelveknek nevezzük . Megmutatható, hogy egy L nyelv akkor és csak akkor csillag nélküli nyelv, ha szintaktikai monoidja aperiodikus [ [4] .

Lásd még

Jegyzetek

  1. ↑ Sakarovitch, 2009 , p. 342.
  2. ↑ 12 Eggan , 1963 .
  3. ↑ Sakarovitch 12 , 2009 .
  4. ↑ Schützenberger, 1965 .

Irodalom