Polinomok értékkészlete minden számrendszerben
nem környezet-független, vagy reguláris

Pontos bibliográfiai adatok:
Horváth Sándor. Ranges of polinomials are not context-free in any number system. To appear in PuMa, June 1998.

Rövid cím: Polinomok értékkészletéről.

Tekintsünk egy egészeken értelmezett p polinomot és egy B ł 1 számot! Definiáljunk egy L nyelvet a következőképp: a nyelv szavai a p polinom értékkészletének nemnegatív egész elemei B alapú számrendszerben felírva. A cikk azzal foglalkozik, hogy az ily módon kapott L nyelvek mely Chomsky osztályokba tartozhatnak. Az eredmény az, hogy (a polinomra tett bizonyos megkötések mellett) elsőfokú polinom esetén a nyelv reguláris, magasabb fokszám esetén pedig nem környezet-független, de környezetfüggő, függetlenül a számrendszer alapjától és a polinomtól.

Formálisan, ha p egy polinom, és B ł 1 egy szám, akkor jelölje L(p,B) = (p(N)ÇN)_B, ahol az alsó index B a B alapú számrendszerben való felírást jelenti, N = {0,1,2,Ľ}.

Tétel. Legyen p(x) = a_rx^r+Ľ+a₁x+a₀ egy tetszőleges egész-együtthatós polinom, melyre r ł 1 és a_r > 0, továbbá legyen B ł 1 egész! Ekkor L(p,B) nem környezet-független, ha r ł 2, és reguláris, ha r = 1.

A tétel bizonyításában a cikk elsősorban a Bar-Hillel lemmára, illetve véges automaták elemi tulajdonságaira hivatkozik. A bizonyítás szétválik az r ł 3, r = 2 és r = 1 esetekre, miközben felhasznál két egyszerű lemmát.

A cikk második részében az előző tétel erősebb változata szerepel: Belátjuk, hogy a polinomra tett feltételek gyengítése mellett is teljesül az állítás. Nevezetesen a polinom lehet tetszőleges komplex együtthatós, amennyiben p(n) Î N teljesül véges sok kivételével minden n Î N esetén.

A dolgozat egy sejtéssel zárul, melyben a polinomra tett megszorítás még gyengébb, és az állítás továbbra is az, hogy L(p,B) sohasem lehet nem reguláris környezet-független.

Egy ,,kicserélési lemma'' környezet-független nyelvekre

Pontos bibliográfiai adatok:
William Ogden, Rockford J. Ross, and Karl Winklmann. An ``interchange lemma'' for context-free languages. SIAM Journal on Computing, 14(2):410-415, May 1985.

Rövid cím: Kicserélési lemma.

A cikk egy új szükséges feltételt ad környezet-független nyelvekre, majd példát is ad az alkalmazására: a lemma segítségével belátja, hogy nem környezet-független egy olyan nyelvről, amely sokáig ellenállt minden hasonló bizonyítási kísérletnek.

Tétel. Legyen L egy T abc-jű környezet-független nyelv. Ekkor létezik olyan c > 0 konstans, hogy minden n ł 2 egészre, minden Q Í L ÇTⁿ halmazra és minden olyan m egészre, melyre n ł m ł 2 létezik k ł |Q|/(cn²) egész és z₁,Ľ, z_k Î Q szavak a következő tulajdonságokkal:

1. z_i = w_ix_iy_i, i = 1,Ľ, k,
2. |w₁| = |w₂| = Ľ = |w_k|,
3. |y₁| = |y₂| = Ľ = |y_k|,
4. m ł |x₁| = |x₂| = Ľ = |x_k| > m/2, és
5. w_ix_jy_i Î L minden i,j Î {1,2,Ľ, k} esetén.

A bizonyítás Chomsky normálformában levő nyelvtanokhoz tartozó levezetési fák levelei számlálásának segítségével történik.

A cikk az alkalmazásra is példát ad: megmutatja, hogy a ,,dadogó'' szavak (azaz az xyyz alakú szavak, ahol y nem üres) nyelve hárombetűs abc felett nem környezet-független.

Primitív szavak nyelve

Pontos bibliográfiai adatok:
P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, and M. Katsura. Formal languages consisting of primitive words. Lecture Notes in Computer Science, 710:194-, 1993.

Rövid cím: Primitív szavak nyelve.

Megjegyzés: A cikket ketten is előadhatják.

Jelöljük Q-val a primitív szavak nyelvét, azaz azokat a szavakat, amelyek nem állnak elő más szó hatványaként. (Formálisan Q = T⁺\{w^m | w Î T^*, m ł 2}, ahol T egy legalább kétbetűs abc.) Sokat kutatott téma, hogy vajon Q környezet-független-e, a sejtés az, hogy nem. Jelen cikk nem dönti el a kérdést, de megmutatja, hogy Q teljesít két erős feltételt, mindkettő szükséges feltétele a környezet-független nyelveknek.

Az első feltétel Bader és Moura feltételének erősítése (erős BM feltétel). Minden környezet-független nyelv rendelkezik a következő tulajdonsággal:

Definíció. Legyen L Í T^* egy nyelv. Akkor mondjuk, hogy L teljesíti az erős BM feltételt, ha létezik olyan n ł 2 egész, hogy minden z Î L szóra, ha z-ben d pozíció kitüntetett és e ł 0 pozíció kizárt, ahol d > n^1+e, akkor z faktorizálható a következő módon: z = uvwxy, ahol

1. w tartalmaz kitüntetett pozíciót,
2. vagy u és v, vagy x és y mindegyike tartalmaz kitüntetett pozíciót,
3. vx nem tartalmaz kizárt pozíciót,
4. ha a kitüntetett és kizárt pozíciók száma vwx-ben rendre r és s, akkor r Ł n^1+s, végül
5. minden m ł 0 számra uv^mwx^my Î L.

Figyeljük meg, hogy d = |z|, e = 0 választással a jól ismert Bar-Hillel lemmát kapjuk. A cikk szerzői belátják, hogy Q teljesíti az erős BM feltételt.

A cikk további részében a szerzők megmutatják, hogy Q egy speciális részhalmaza nem környezet-független, de megadnak végtelen sok olyan reguláris R nyelvet, melyekre QÇR környezet-független.

A primitív szavak nyelve erősen kicserélhető, de nem lineáris

Pontos bibliográfiai adatok:
Horváth Sándor. Primitive words are strongly interchangeable but nonlinear. Technical Report FBI-HH-B-183/96, Universität Hamburg Fachbereich Informatik, Vogt-Kölnn-Strasse 30, D-22527 Hamburg, Germany, January 1996.

Rövid cím: Erős kicserélhetőség.

Jelöljük Q-val a primitív szavak nyelvét, azaz azokat a szavakat, amelyek nem állnak elő más szó hatványaként. (Formálisan Q = T⁺\{w^m | w Î T^*, m ł 2}, ahol T egy legalább kétbetűs abc.) Sokat kutatott téma, hogy vajon Q környezet-független-e, a sejtés az, hogy nem. Jelen cikk nem dönti el a kérdést, de négy eredményt közül, ami közelebb hozhatja a megoldást.

A szerző bevezeti az Ogden, Ross és Winklmann kicserélési tulajdonságának egy erősített változatát, majd megmutatja hogy Q rendelkezik ezzel a tulajdonsággal.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv erősen kicserélhető, ha létezik olyan c > 0 konstans, melyre minden n ł 2, i ł 0 és j ł 1 esetén, ahol j < n és i+j Ł n, és minden H Í LÇTⁿ nem üres halmazra létezik H˘ Í H a következő tulajdonságokkal:

1. |H˘| > |H|/c
2. x,y Î H˘ esetén, ha x = x₁x₂x₃, y = y₁y₂y₃, ahol |x₁| = |y₁| = i, |x₂| = |y₂| = j, teljesül a következő: x₁y₂x₃, y₁x₂y₃ Î L.

A dolgozat további részében a szerző bizonyítja, hogy a legfeljebb n hosszú primitív szavak sűrűsége exponenciális gyorsasággal tart 0-hoz n növekedtével, valamint azt, hogy Q nem korlátos nyelv, és nem is lineáris.

Szavak kombinatorikus tulajdonságai és a Chomsky osztályok kapcsolata

Pontos bibliográfiai adatok:
Dömösi Pál et al. Some combinatorial properties of words, and the Chomsky hierarchy. In Proc. Internat. Conf. ``Words, Languages and Combinatorics, II'', Kyoto, Japan; eds.: M. Ito and H. Jürgensen, pages 105-123. Singapore: World Scientific, 1992.

Rövid cím: Kombinatorikus tulajdonságok.

Megjegyzés: A cikket ketten is előadhatják.

Jelöljük Q-val a primitív szavak nyelvét, azaz azokat a szavakat, amelyek nem állnak elő más szó hatványaként. (Formálisan Q = T⁺\{w^m | w Î T^*, m ł 2}, ahol T egy legalább kétbetűs abc.) Sokat kutatott téma, hogy vajon Q környezet-független-e, a sejtés az, hogy nem. Jelen cikk nem dönti el a kérdést, de belátja, hogy Q teljesít három olyan feltételt, az Ogden, az erős Bader-Moura és a Sokolowsky feltételt, amelyet minden környezet-független nyelv teljesít. A cikk egy negyedik feltételt is vizsgál, ami szükséges feltétele minden környezet-független nyelvnek, a Parikh szemilinearitást. Megmutatja, hogy QÇ(a^*b)ⁿ (ahol n ł 1 egész) Parikh szemilineáris, tehát ez a támadási kísérlet is kudarcot vall. A dolgozat utolsó része általánosan vizsgál bizonyos nyelvi tulajdonságokat, különös tekintettel azok eldönthetőségére és elhelyezkedésükre a Kleene féle aritmetikai hierarchiában.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Ogden feltételt, ha létezik olyan n ł 2 egész, melyre z Î L esetén, ha legalább n+1 pozíciót z-ben kitüntetettnek tekintünk, akkor z felbontható z = uvwxy alakban, ahol teljesülnek a következők:

1. vagy u, v és w, vagy w, x és y mindegyike tartalmaz kitüntetett pozíciót,
2. vwx legfeljebb n kitüntetett pozíciót tartalmaz,
3. minden m ł 0 számra uv^mwx^my Î L.

Tétel. Minden környezet-független nyelv teljesíti az Ogden feltételt.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Sokolowsky feltételt, ha minden Y Í T^*, |Y| ł 2, és minden u₁, u₂, u₃ Î T^* esetén, ha {u₁xu₂xu₃ | x Î Y⁺} Í L, akkor létezik olyan x˘,x˘˘ Î Y⁺, x˘ ą x˘˘, melyre u₁x˘u₂x˘˘u₃ Î L.

Tétel. Minden környezet-független nyelv teljesíti a Sokolowsky feltételt.

Környezet-független nyelvekre adott kicserélési és pumpáló lemmák

Pontos bibliográfiai adatok:
R. Boonyavatana and G. Slutzki. The interchange or pump (DI)lemmas for context-free languages. Theoretical Computer Science, 56(3):321-338, March 1988.

Rövid cím: Feltételek összehasonlítása.

Megjegyzés: A cikket ketten is előadhatják.

A cikk összehasonlítja a kicserélési lemmát különböző pumpáló lemmákkal: a Bar-Hillel félével, Ogdenével, ennek általánosított változatával, a fentiek lineáris változatával, valamint a Sokolowsky féle feltételekkel. Ezen felül definiál egy kicserélési feltételt lineáris környezet-független nyelvekre, és összehasonlítja a többi feltétellel. Az eredmények megmutatják, hogy a kicserélési feltételek nem összehasonlíthatóak a pumpáló feltételekkel és a kiterjesztett Sokolowsky feltétellel, de határozottan erősebbek a Sokolowsky feltételnél.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a lineáris kicserélési feltételt, ha létezik olyan c > 0 konstans, hogy minden n ł m ł 2 egészekre, és minden Q Í L ÇTⁿ halmazra létezik R Í Q a következő tulajdonságokkal:

1. |R| ł |Q|/(cn), és
2. valamilyen i ł 0 számra {xwy | $u,v,z Î T^* : |x| = |u| = i, |w| = |z| = m, xzy,uwv Î R} Í LÇTⁿ.

Definíció. Azt mondjuk, hogy egy R Í T^*×T^* reláció nem korlátos, ha minden m számra léteznek olyan x,y Î T^* szavak, melyre |x|,|y| ł m, és R(x,y) fennáll.

Definíció. x,y Î T^* esetén x < y azt jelenti, hogy x-et úgy kaphatjuk y-ból, hogy néhány betűjét kitöröljük. Ha a törölt szimbólumok y utolsó (első) m szimbóluma közül kerülnek ki, azt így jelöljük: x < ^my (x  ^m < y). Szavak párjaira definiáljuk a következő relációt:

(x˘,y˘) < m (x,y) Ű (x˘ < xŮy˘ = y) Ú(x˘ = xŮy˘ < y) Ú(x˘ < m x Ůy˘ m < y).

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a kiterjesztett Sokolowsky feltételt, ha minden u₁,u₂,u₃ Î T^* szóra és minden R Í T^*×T^* nem korlátos relációra, ha {u₁xu₂yu₃ | R(x,y)} Í L, akkor létezik olyan m egész, hogy minden x,y Î T^* esetén

|x|,|y| > m Ů R(x,y)\implies$x˘,y˘: (x˘,y˘) < m (x,y) Ů u1x˘u2y˘u3 Î L.

A rekurzívan felsorolható nyelvek jellemzése beszúró-törlő rendszerek segítségével

Pontos bibliográfiai adatok:
Lila Kari, Gheorghe Paun, Gabriel Thierrin, and Sheng Yu. At the crossroads of dna computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, held at the University of Pennsylvania, June 23 - 25, 1997, pages 318-333, June 1997.

Rövid cím: Beszúró-törlő rendszerek.

Megjegyzés: A cikket ketten is előadhatják.

A formális nyelvek elméletében a leggyakoribb generáló mechanizmus az újraírás. A természetes nyelvek vizsgálata során merült fel a gondolat, hogy az újraírás mellett, vagy helyett szövegrészek beszúrásával, vagy törlésével képezzünk új szövegeket. E módszerek a molekuláris számítások szempontjából is rendkívül fontosak, mert különböző enzimek segítségével DNS, illetve RNS molekulákon megvalósíthatóak bizonyos (a környezettől is függő) beszúrások és törlések. A cikk a beszúró-törlő rendszerek több alosztályáról belátja, hogy az általuk generált nyelv megegyezik a rekurzívan felsorolható nyelvekkel.

Definíció. Beszúró-törlő rendszeren a következő konstrukciót értjük:

g = (V,T,A,I,D),

ahol V egy abc, T Í V, A Í V^*, I,D Í V^*×V^*×V^* véges halmazok.

T a rendszerünk terminális abc-je, A az axiómák, I a beszúró, D a törlő szabályok halmaza. (u,z,v) Î I azt jelenti, hogy ha egy szóban előfordul az uv részszó, akkor u és v közé beszúrhatjuk a z szót. (u,z,v) Î D azt jelenti, hogy ha egy szóban előfordul az uzv részszó, akkor u és v közül kitörölhetjük a z szót.

x,y Î V^* esetén xŢy pontosan akkor áll fenn, ha a következők egyike teljesül:

• x = x₁uvx₂, y = x₁uzvx₂, x₁, x₂ Î V^* és (u,z,v) Î I
• x = x₁uzvx₂, y = x₁uvx₂, x₁, x₂ Î V^* és (u,z,v) Î D

Jelölje Ţ^* a Ţ reláció reflexív, tranzitív lezártját. A g által generált nyelv:

L(g) = {w Î T* | xŢ* w, x Î A}.

A reverzibilis két-számlálójú gép univerzalitásáról

Pontos bibliográfiai adatok:
Kenichi Morita. Universality of a reversible two-counter machine. Theoretical Computer Science, 168(2):303-320, 20 November 1996.

Rövid cím: Két-számlálójú gép.

Megjegyzés: A cikket ketten is előadhatják.

A k-számlálójú gép (CM(k)) egy olyan automata, aminek k számláló áll rendelkezésre segédmemóriaként. Minsky megmutatta, hogy bármely Turing gépet lehet szimulálni egy CM(2)-beli géppel. Ez a cikk a reverzibilis (visszafelé determinisztikus) számláló gépekkel foglalkozik. Először megmutatja, hogy bármely CM(k) gép szimulálható egy reverzibilis CM(k+2) géppel, majd bebizonyítja, hogy minden reverzibilis CM(k) gép szimulálható egy reverzibilis CM(2)-belivel.

Definíció. k-számlálójú gép alatt a következőt értjük:

M = (k,Q,d,q0,qf),

ahol k a szalagok (vagy számlálók) száma, Q az állapotok véges, nem üres halmaza, q₀ Î Q a kezdőállapot, q_f Î Q a végső állapot. A szalagok abc-je {Z,P}, ahol P az üres szimbólum. d a konfiguráció-átmeneti reláció: d Í (Q×{1,Ľ,k}×{Z,P}×Q)Č(Q×{1,Ľ,k}×{-,0,+}×Q). A -, 0, + szimbólumok balra mozgást, helyben maradást, illetve jobbra mozgást jelentenek. A szalagok egy irányba (jobbra) végtelen hosszúak, a legbaloldali pozícióban a Z szimbólum szerepel, az összes többiben pedig a P. (Z a zérus, P a pozitív rövidítése.)

d minden eleme egy négyes, alakja vagy (q,i,s,q˘), vagy (q,i,d,q˘), ahol q,q˘ Î Q, s Î {Z,P}, d Î {-,0,+}. A (q,i,s,q˘) négyes azt jelenti, hogy ha a gép a q állapotban van, és az i. olvasófej alatt az s szimbólum található, akkor átmehet a q˘ állapotba. A (q,i,d,q˘) négyes azt jelenti, hogy ha a gép a q állapotban van, átmehet a q˘ állapotba, és az i. olvasófej balra, jobbra, vagy nem mozog egy pozíciót d értéke szerint.

Nyelvek generálása kétfajta zárójelpár segítségével

Pontos bibliográfiai adatok:
Viliam Geffert. How to generate languages using only two pairs of parentheses. EIK: Journal of Information Processing and Cybernetics EIK (formerly Elektronische Informationsverarbeitung und Kybernetik), 27, 1991.

Rövid cím: Geffert normálforma.

Megjegyzés: A cikket ketten is előadhatják.

A szerző két jól használható normálformát ad a 0. típusú nyelvtanokra.

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G˘ nyelvtan, melynek idő- és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S˘,(,),[,]), szabályai kettő kivételével környezet-függetlenek. (A két kivétel: ()®e, és []®e.)

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G˘ nyelvtan, melynek idő- és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S˘,X,A,B,C), szabályai egy kivételével környezet-függetlenek. (A kivétel: ABC®e.)

Formális nyelvek szeminárium, 2000

Tervezett program

A [3], [5], [6], [7], [8], [9] cikkeket ketten is előadhatják.

Szükséges feltételek környezet-független nyelvekre

[1]

Horváth Sándor. Ranges of polinomials are not context-free in any number system. To appear in PuMa, June 1998.

[2]

William Ogden, Rockford J. Ross, and Karl Winklmann. An ``interchange lemma'' for context-free languages. SIAM Journal on Computing, 14(2):410-415, May 1985.

[3]

P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, and M. Katsura. Formal languages consisting of primitive words. Lecture Notes in Computer Science, 710:194-, 1993.

[4]

Horváth Sándor. Primitive words are strongly interchangeable but nonlinear. Technical Report FBI-HH-B-183/96, Universität Hamburg Fachbereich Informatik, Vogt-Kölnn-Strasse 30, D-22527 Hamburg, Germany, January 1996.

[5]

Dömösi Pál et al. Some combinatorial properties of words, and the Chomsky hierarchy. In Proc. Internat. Conf. ``Words, Languages and Combinatorics, II'', Kyoto, Japan; eds.: M. Ito and H. Jürgensen, pages 105-123. Singapore: World Scientific, 1992.

[6]

R. Boonyavatana and G. Slutzki. The interchange or pump (DI)lemmas for context-free languages. Theoretical Computer Science, 56(3):321-338, March 1988.

Egyéb témák

[7]

Lila Kari, Gheorghe Paun, Gabriel Thierrin, and Sheng Yu. At the crossroads of dna computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, held at the University of Pennsylvania, June 23 - 25, 1997, pages 318-333, June 1997.

[8]

Viliam Geffert. How to generate languages using only two pairs of parentheses. EIK: Journal of Information Processing and Cybernetics EIK (formerly Elektronische Informationsverarbeitung und Kybernetik), 27, 1991.

[9]

Kenichi Morita. Universality of a reversible two-counter machine. Theoretical Computer Science, 168(2):303-320, 20 November 1996.

Tartalék cikkek

[10]

Arto Salomaa. Abstact Families of Languages, In: Formal Languages, chapter IV, pages 123-141. Academic Press, New York, 1973.

[11]

Arto Salomaa. Finite non-deterministic and probabilistic automata, In: Theory of Automata, chapter II, pages 71-93. Pergamon Press, 1969.

Vissza a Formális nyelvek és automaták szeminárium lapjára.