Relations defined by n-tape automata.
Karel Čulík · Czech digital mathematics library · 1967
Relace representované tz-páskovými automaty KAREL CULÍK II V článku jsou vyšetřovány třídy relací representované různými třídami n-páskových automatů.Je zavedena representace relace mod e n-páskovým automatem a jsou vyšetřovány třídy relací representované mod e n-páskovými automaty.Zkoumají se hlavně inkluse různých tříd relací representovaných třídami automatů a jejich uzavřenost vůči booleovským a Kleeneho operacím.0. ÚVOD V práci jsou vyšetřovány třídy relací representované (definované) n-páskovými automaty.Auto matem se zde rozumí automat bez výstupu s vytčenou množinou koncových stavů, který je určen k tomu, aby rozeznával přijaté a nepřijaté n-tice slov nad zvolenou abecedou Z. Uvažuje se třída automatů D B , zavedená pro n = 2 v [4] a [6], a její nedeterminovaná verse N n , třídy E n , S n a M n , zavedené v [5] a nově zavedené třídy G n a H n .V práci jsou vyšetřovány relace a třídy relací representované uvedenými třídami n-páskových konečných automatů.Práce navazuje na [4], [5] a [6].Zkoumají se hlavně inkluse různých tříd relací representovaných třídami automatů a jejich uzavřenost vůči booleovským a Kleeneho ope racím.Jsou rovněž vyšetřovány relace a třídy relací representované mod e n-páskovými automaty.Definice representace mod e pro relace je analogická definici representace mod e pro jazyky v [3].Výsledky o inklusích, rovnostech a neinklusích uvažovaných tříd relací jsou shrnuty v přehled ném diagramu na obr. 5 a odvozené výsledky o uzavřenosti těchto tříd jsou spolu s výsledky zná mými z literatury ([4], [5], [6]) uvedeny v tabulce 5. Uvedeme několik méně běžných pojmů a označení, resp.upřesníme význam, ve kterém je budeme používat.Zvolme pevně nějakou abecedu 27.1 je konečná množina tzv.symbolů.Slovo nad abecedou S je sřetězení konečně mnoha symbolů z abecedy Z. Prázdné slovo ozna čujeme e. (Rovněž tak budeme označovat tzv."prázdný" symbol e $ I.) Jazyk nad abecedou I 1 je množina slov nad abecedou I. n-ární relace nad abecedou Z je množina n-tic slov nad abecedou I. Množinu všech slov (včetně prázdného) nad abecedou I označme I*.Množinu všech n-tic slov nad abecedou I označme (l*) n .Jestliže p a q jsou slova nad abecedou I, p = a x ... a s , q = b t ... b t (a t el, i = = 1,2,..., s; b.el', i = 1, 2, .... t), pak sřetězením slov p a q rozumíme slovo a x ... a s b x ... b t a označujeme ho ps nebo p .s. Nechť u e (X*) n , v e (!*)", u = (u u u 2 , ..Množinu prvků, které mají vlastnost V, označujeme {x : x má vlastnost V}, chceme-li zdůraznit, že je takto definována množina M, píšeme M = {x : x má vlast nost V}.