Substituce a morfismy jednoduˇse Petr Zemek∗ 31. ˇcervence 2010†
Abstrakt Tento text si d´ av´ a za c´ıl srozumitelnˇe a formou pˇr´ıklad˚ u osvˇetlit problematiku substituc´ı a morfism˚ u v rozsahu pˇredmˇetu Teoretick´ a informatika (TIN) v magistersk´ ych studijn´ıch oborech na Fakultˇe informaˇcn´ıch technologi´ı v Brnˇe (FIT). Jsou prezentov´ any dvˇe verze v´ ykladu: neform´ aln´ı a form´ aln´ı.
´ Uvod
1
Bˇehem m´eho studia na FITu, at’ jiˇz pˇri absolvov´an´ı pˇredmˇetu TIN ˇci pˇri pˇr´ıpravˇe na st´atn´ı z´avˇereˇcnou zkouˇsku jsem nabyl dojmu, ˇze problematika substituc´ı, morfism˚ u a uzavˇrenost´ı jazykov´ ych tˇr´ıd vzhledem k tˇemto operac´ım neb´ yv´ a dostateˇcnˇe pochopena. T´ımto textem bych to chtˇel napravit, protoˇze si mysl´ım, ˇze po vhodn´em vysvˇetlen´ı na tom nen´ı nic sloˇzit´eho ;). V´ yklad a pouˇzit´e konvence budou zaloˇzeny na studijn´ı opoˇre do TINu [5], konkr´etnˇe sekci 5.5.2 (Uz´ avˇerov´e vlastnosti bezkontextov´ ych jazyk˚ u). Budu prezentovat dvˇe verze. Nejdˇr´ıve vˇse pop´ıˇsi neform´ alnˇe a ilustruji to na pˇr´ıkladech a pot´e to zformalizuji. Form´aln´ı verze je zaloˇzena na knih´ach [2] (strany 49–51) a [4] (strany 71 a 423–424), jejichˇz v´ yklad se mi zd´a vhodnˇejˇs´ı, neˇz ten, kter´ y je prezentov´ an v opoˇre k TINu. K pochopen´ı t´eto problematiky bude ovˇsem staˇcit porozumˇet m´emu neform´ aln´ımu v´ ykladu.
2
Substituce a morfismy neform´ alnˇ e
Abych neform´ aln´ı ˇc´ ast co nejv´ıce zjednoduˇsil, tak se omez´ım pouze na bezkontextov´e gramatiky a bezkontextov´e jazyky – z pohledu TINu na to stejnˇe byl kladen nejvˇetˇs´ı d˚ uraz. Je tˇreba si ale uvˇedomit to, ˇze tyto koncepty jsou univerz´aln´ı, ˇcili se vztahuj´ı i na ostatn´ı jazykov´e tˇr´ıdy.
2.1
Substituce
Pojem substituce lze ch´ apat jako nahrazen´ı. V naˇsem pˇr´ıpadˇe nahrad´ıme kaˇzd´ y symbol nˇejakou mnoˇzinou ˇretˇezc˚ u, tedy jazykem. Vezmˇeme si napˇr. ˇretˇezec ab a substituci σ (sigma), kter´a je definov´ ana n´ asledovnˇe: σ(a) = {0, 00} a σ(b) = {1, 111, 1110}. (2.1) Znamen´ a to, ˇze kaˇzd´e a se nahrad´ı jazykem {0, 00} a kaˇzd´e b se nahrad´ı jazykem {1, 111, 1110}. Pˇri aplikaci substituce na ˇretˇezec se tato substituce aplikuje na kaˇzd´ y symbol zvl´aˇst’, ˇcili v pˇr´ıpadˇe ˇretˇezce ab dostaneme σ(ab) = σ(a)σ(b) = {0, 00}{1, 111, 1110}, ∗ Fakulta
informaˇ cn´ıch technologi´ı, Vysok´ e uˇ cen´ı technick´ e v Brnˇ e, e-mail:
[email protected] revize: 4. listopadu 2015
† Posledn´ ı
1
coˇz n´ am po proveden´ı konkatenace d´ a σ(ab) = {01, 0111, 01110, 001, 00111, 001110}. Jelikoˇz jsou oba jazyky v (2.1) koneˇcn´e, tak se jedn´a s koneˇcnou substituci. Obecnˇe ale nemus´ı b´ yt substituce koneˇcn´ a. Vezmˇeme si napˇr. substituci definovanou takto: σ(a) = {0n 1n | n ≥ 0} a σ(b) = {0}∗ .
(2.2)
Tato substituce je nekoneˇcn´ a. Po jej´ım aplikov´an´ı na ab dostaneme σ(ab) = σ(a)σ(b) = {0n 1n | n ≥ 0}{0}∗ , coˇz n´ am ve v´ ysledku d´ a jazyk σ(ab) = {0n 1n 0m | m, n ≥ 0}. V obou pˇr´ıpadech jsme substituci aplikovali na jedin´ y ˇretˇezec. Substituci lze ale aplikovat i na jazyk (ten m˚ uˇze b´ yt i nekoneˇcn´ y), a to tak, ˇze se aplikuje na kaˇzd´ y ˇretˇezec z tohoto jazyka a v´ ysledky se sjednot´ı. Vezmˇeme si jazyk σ(a) z (2.2) a oznaˇcme jej L, ˇcili L = {an bn | n ≥ 0},
(2.3)
a substituci definovanou n´ asledovnˇe: σ(a) = La a σ(b) = Lb , kde La = {0, 1} a Lb = {dd, ee, f f f, ggg}. Pro jednoduchost jsem zvolil koneˇcnou substituci (La i Lb jsou koneˇcn´e jazyky). Po aplikaci σ na L dostaneme jazyk [ [ σ(L) = Lna Lnb = {0, 1}n {dd, ee, f f f, ggg}n . (2.4) n≥0
n≥0
Do jazyka (2.4) tedy patˇr´ı ˇretˇezce ε, 00ddee, 1f f f , 010gggdddd, 1111ddddgggee apod. Pokud bych to mˇel shrnout, tak substituce n´am definuje nahrazen´ı kaˇzd´eho symbolu nˇejak´ ym jazykem. Substituce aplikovan´ a na ˇretˇezec je definovan´a tak, ˇze se aplikuje na kaˇzd´ y symbol v tomto ˇretˇezci. A koneˇcnˇe, pokud aplikujeme substituci na jazyk, pak se substituce aplikuje na kaˇzd´ y ˇretˇezec z tohoto jazyka a v´ ysledky se sjednot´ı.
2.2
Morfismy
Morfismus je speci´ aln´ı pˇr´ıpad substituce, kde kaˇzd´ y jazyk obsahuje pouze jedin´ y ˇretˇezec. Pro odliˇsen´ı budu morfismy oznaˇcovat ϕ ( f´ı“). M˚ uˇzeme si tedy zjednoduˇsit z´apis, a to tak, ˇze m´ısto ” ϕ(a) = {w} budeme ps´ at jen ϕ(a) = w, kde w je ˇretˇezec. Pojd’me si uk´ azat pˇr´ıklad. Mˇejme morfismus definovan´ y n´asledovnˇe: ϕ(a) = 00, ϕ(b) = 01 a ϕ(c) = 10. Pak napˇr. ϕ(abac) = ϕ(a)ϕ(b)ϕ(a)ϕ(c) = 00010010. 2
(2.5)
Vid´ıme, ˇze na rozd´ıl od substituce je v´ ysledek aplikov´an´ı morfismu vˇzdy jednoznaˇcn´ y (vˇzdy dostaneme jedin´ y ˇretˇezec). D´ a se ˇr´ıct, ˇze morfismus n´am ˇretˇezec pouze nˇejak pˇrek´oduje. Pˇekn´ ym pˇr´ıkladem morfismu je tzv. Morse˚ uv k´ od 1 , kter´ y je pouˇz´ıv´an v telegrafii. Kaˇzd´e p´ısmeno latinsk´e abecedy se k´ oduje do posloupnosti znak˚ u · (teˇcka) a - (pomlˇcka). Pro n´azornost uvedu jen k´odov´an´ı p´ ar symbol˚ u: ϕ(a) = ·ϕ(b) = - · · · ϕ(c) = - · -· ··· ˇ ezec aab se pak zak´ Retˇ oduje do ϕ(aab) = ϕ(a)ϕ(a)ϕ(b) = ·- · -- · · · . Pomoc´ı morfismu mohu nˇekter´e znaky vymazat, ˇcili nahradit pr´azdn´ ym ˇretˇezcem. Dejme tomu, ˇze bych chtˇel z libovoln´eho ˇretˇezce znak˚ u 0 a 1 odstranit vˇsechny znaky 1. Lze toho doc´ılit pomoc´ı morfismu ϕ definovan´ ym jako ϕ(0) = 0 a ϕ(1) = ε. Skuteˇcnˇe, ϕ(0110001) = ϕ(0)ϕ(1)ϕ(1)ϕ(0)ϕ(0)ϕ(0)ϕ(1) = 0000. Dalˇs´ım vyuˇzit´ım morfism˚ u je pˇr´ıpad, kdy chci nˇekter´e znaky pˇreznaˇcit. Dejme tomu, budu m´ıt mnoˇzinu netermin´ al˚ u N = {A, B, C} a mnoˇzinu termin´al˚ u Σ = {a, b, c} a j´a chci kaˇzd´ y netermin´al nahradit jeho ˇc´ arkovanou verz´ı, tj. m´ısto A budu m´ıt A0 atd. Pr´avˇe toto dˇel´a n´asleduj´ıc´ı morfismus: ϕ(A) = A0 , ϕ(B) = B 0 , ϕ(C) = C 0 , ϕ(a) = a, ϕ(b) = b a ϕ(c) = c. Jak vid´ıte, tak s pˇrib´ yvaj´ıc´ım mnoˇzstv´ım znak˚ u n´am roste sloˇzitost popisu. V podobn´ ych pˇr´ıpadech lze s v´ yhodou vyuˇz´ıt n´ asleduj´ıc´ıho ekvivalentn´ıho popisu: definujme morfismus ϕ tak, ˇze ϕ(X) = X 0 pro vˇsechna X ∈ N a ϕ(x) = x pro vˇsechna x ∈ Σ. U morfismu jazyka je to obdobn´e jako u substituce. Jelikoˇz ale pro kaˇzd´ y ˇretˇezec existuje pr´avˇe jeden zak´ odovan´ y ˇretˇezec, tak je to jednoduˇsˇs´ı. Pokud si vezmeme jazyk L z (2.3) a morfismus definovan´ y v (2.5), tak ϕ(L) = ϕ {an bn | n ≥ 0} = (00)n (01)n | n ≥ 0 . (2.6) Do jazyka (2.6) patˇr´ı napˇr. ˇretˇezce ε, 0001 a 00000101.
2.3
Uzavˇ renost tˇ r´ıdy bezkontextov´ ych jazyk˚ u
Nejdˇr´ıve si mus´ıme vysvˇetlit, co je to tzv. bezkontextov´ a substituce. Ta je definov´ana obdobnˇe jako koneˇcn´ a a nekoneˇcn´ a substituce, ˇcili bezkontextov´a substituce je takov´a substituce, kde je kaˇzd´ y symbol nahrazen bezkontextov´ ym jazykem. Vˇsechny substituce ze sekce 2.1 jsou bezkontextov´e. Ovˇsem napˇr. n´ asleduj´ıc´ı substituce σ(0) = {an bn cn | n ≥ 0} a σ(1) = {c, d} bezkontextov´ a nen´ı, protoˇze jazyk {an bn cn | n ≥ 0} patˇr´ı mezi zn´am´e jazyky, kter´e bezkontextov´e nejsou. Tˇr´ıda bezkontextov´ ych jazyk˚ u je uzavˇrena v˚ uˇci substituci, pokud kdyˇz si vezmeme libovoln´ y bezkontextov´ y jazyk L a libovolnou bezkontextovou substituci σ, tak σ(L) je bezkontextov´ y jazyk. Ted’ se pokus´ım m´enˇe form´ alnˇe pˇreformulovat d˚ ukazy vˇet 5.10 a 5.11 z [5] (d´am hlavn´ı ideu). 1 http://cs.wikipedia.org/wiki/Morseova
abeceda
3
Vˇ eta 1. Tˇr´ıda bezkontextov´ych jazyk˚ u je uzavˇrena v˚ uˇci substituci. D˚ ukaz. Vezmeme si libovoln´ y bezkontextov´ y jazyk L a libovolnou bezkontextovou substituci σ. Ted’ mus´ıme uk´ azat, ˇze σ(L) je bezkontextov´ y jazyk. Jelikoˇz je L bezkontextov´ y, tak existuje bezkontextov´ y gramatika G = (N, Σ, P, S), kter´a jej generuje. D˚ ukaz je zaloˇzen na tom, ˇze jelikoˇz je σ bezkontextov´ a substituce, tak pro kaˇzd´ y termin´al a ∈ Σ existuje bezkontextov´a gramatika Ga = (Na , Σa , Pa , Sa ), kter´ a generuje σ(a). Vytvoˇr´ıme tedy novou gramatiku G0 tak, ˇze kaˇzd´ y termin´ al a na prav´e stranˇe kaˇzd´eho pravidla v P nahrad´ıme startuj´ıc´ım netermin´alem Sa . Napˇr. pro pravidlo A → aBc dostaneme pravidlo A → Sa BSc . Jakmile by tedy v p˚ uvodn´ı gramatice doˇslo k vygenerov´ an´ı termin´ alu, tak m´ısto nˇej se vygeneruje startuj´ıc´ı netermin´al pˇr´ısluˇsn´e gramatiky. Z toho se pak vygeneruje ˇretˇezec z pˇr´ısluˇsn´eho jazyka (pro termin´al a to bude ˇretˇezec z jazyka σ(a) atp.). Uzavˇrenost tˇr´ıdy bezkontextov´ ych jazyk˚ u v˚ uˇci morfismu je definovan´a obdobnˇe. Pokud si vezmeme libovoln´ y bezkontextov´ y jazyk L a libovoln´ y morfismus ϕ, tak ϕ(L) mus´ı b´ yt tak´e bezkontextov´ y jazyk. Vˇsimnˇete si, ˇze nepoˇzaduji nic takov´eho, aby ϕ byl bezkontextov´ y morfismus“, protoˇze to ” ned´ av´ a smysl. Vˇ eta 2. Tˇr´ıda bezkontextov´ych jazyk˚ u je uzavˇrena v˚ uˇci morfismu. D˚ ukaz. Jelikoˇz je morfismus speci´ aln´ım pˇr´ıpadem substituce, tak tato vˇeta plat´ı ihned d´ıky Vˇetˇe 1. Pokud bychom na to chtˇeli j´ıt konstrukˇcnˇe, ˇcili pro libovoln´ y bezkontextov´ y jazyk L a libovoln´ y morfismus ϕ vytvoˇrit bezkontextovou gramatiku, kter´a generuje ϕ(L), tak bychom postupovali stejnˇe jako v d˚ ukaze Vˇety 1 s t´ım rozd´ılem, ˇze m´ısto nahrazen´ı kaˇzd´eho termin´alu a startuj´ıc´ım netermin´ alem Sa ho pˇr´ımo nahrad´ıme ˇretˇezcem ϕ(a). Tedy napˇr. pokud ϕ(a) = 000 a ϕ(c) = 11, tak pravidlo A → aBc nahrad´ıme pravidlem A → 000B11.
3
Substituce a morfismy form´ alnˇ e ∗
Definice 1. Necht’ Σ a Γ jsou abecedy. Funkce σ : Σ∗ → 2Γ se naz´ yv´a substituce pr´avˇe tehdy, kdyˇz (1) (2)
σ(ε) = {ε}, σ(xy) = σ(x)σ(y) pro vˇsechny ˇretˇezce x, y ∈ Σ∗ . ∗
Aˇc to vypad´ a sloˇzitˇe, tak Σ∗ oznaˇcuje mnoˇzinu vˇsech ˇretˇezc˚ u nad abecedou Σ a 2Γ oznaˇcuje mnoˇzinu vˇsech jazyk˚ u nad abecedou Γ, viz strana 10 v opoˇre k TINu [5]. Podm´ınka (1) se nˇekdy vynech´av´a [2], protoˇze vypl´ yv´ a z podm´ınky (2). Podm´ınka (2) n´am zaruˇcuje, ˇze substituci lze definovat tak, jak jsme si ji neform´ alnˇe definovali v sekci 2.1, ˇcili kaˇzd´emu symbolu pˇriˇrad´ıme jazyk a v pˇr´ıpadˇe ˇretˇezce aplikujeme substituci na kaˇzd´ y z jeho symbol˚ u. Podle definice sice pˇriˇrazujeme jazyk kaˇzd´emu ˇretˇezci, ale jelikoˇz se substituce chov´ a bezkontextovˇe“, tak ji staˇc´ı definovat po jednotliv´ ych symbolech. ” Substituci ˇretˇezce pak dostaneme automaticky. Definice 2. Necht’ Σ a Γ jsou abecedy. Funkce ϕ : Σ∗ → Γ∗ se naz´ yv´a morfismus pr´avˇe tehdy, kdyˇz (1) (2)
ϕ(ε) = ε, ϕ(xy) = ϕ(x)ϕ(y) pro vˇsechny ˇretˇezce x, y ∈ Σ∗ .
Jelikoˇz je morfismus2 pouze speci´ aln´ı pˇr´ıpad substituce, tak je jeho definice velice podobn´a. Takˇze to, co plat´ı pro substituci, plat´ı i pro morfismus. 2 Pozn´ amka pro zv´ıdav´ e: Σ∗ se naz´ yv´ a voln´ y monoid s operac´ı konkatenace a neutr´ aln´ım prvkem ε a onen morfismus je pouze zkr´ acen´ y n´ azev pro homomorfismus nad monoidy, jak jej zn´ ate z MATu. Viz napˇr. sekce 11.1 v [1].
4
Rozˇs´ıˇren´ı substituc´ı a morfism˚ u na jazyky d´av´a n´asleduj´ıc´ı definice. ∗
Definice 3. Necht’ Σ a Γ jsou abecedy, L ⊆ Σ∗ je jazyk nad Σ, σ : Σ∗ → 2Γ je substituce a ϕ : Σ∗ → Γ∗ je morfismus. Pak [ σ(L) = σ(w) w∈L
a ϕ(L) = ϕ(w) | w ∈ L . Koneˇcnˇe, uzavˇrenost jazykov´e tˇr´ıdy v˚ uˇci substituci a morfismu je form´alnˇe definov´ana n´asledovnˇe. Definice 4. Necht’ L je tˇr´ıda jazyk˚ u. L je uzavˇrena v˚ uˇci substituci pr´avˇe tehdy, kdyˇz pro libovoln´ y ∗ jazyk L ∈ L a pro libovolnou substituci σ : Σ∗ → 2Γ takovou, ˇze σ(a) ∈ L pro vˇsechna a ∈ Σ, plat´ı, ˇze σ(L) ∈ L. L je uzavˇrena v˚ uˇci morfismu pr´avˇe tehdy, kdyˇz pro libovoln´ y jazyk L ∈ L a pro libovoln´ y morfismus ϕ : Σ∗ → Γ∗ plat´ı, ˇze ϕ(L) ∈ L.
4
Z´ avˇ er
Substituce nahrazuje kaˇzd´ y symbol jazykem, kdeˇzto morfismus nahrazuje kaˇzd´ y symbol ˇretˇezcem. Morfismus je speci´ aln´ım pˇr´ıpadem substituce. D´ıky vlastnostem substituce a morfismu staˇc´ı, kdyˇz je definujeme pro jednotliv´e symboly, a automaticky je m´ame definov´any pro ˇretˇezce. Rozˇs´ıˇren´ı substituc´ı a morfism˚ u na jazyky je pˇr´ımoˇcar´e. Pevnˇe douf´ am, ˇze se mi tyto koncepty podaˇrilo dostateˇcnˇe objasnit. Vzhledem k tomu, ˇze jsem chtˇel tento text vmˇestnat do max. pˇeti str´anek, tak se sem nevlezla nˇekter´a t´emata, napˇr. inverzn´ı morfismus a uzavˇrenost tˇr´ıdy bezkontextov´ ych jazyk˚ u v˚ uˇci nˇemu. Vˇeˇr´ım ale, ˇze po pochopen´ı tˇechto z´ aklad˚ u pochop´ıte i tento koncept. Z´ ajemc˚ um o rozˇsiˇruj´ıc´ı a obecnˇejˇs´ı koncepty se doporuˇcuji pod´ıvat na koneˇcn´e pˇrevody (finite transduction) a GSM mapov´ an´ı (GSM mapping, od Generalized Sequential Machine), viz napˇr. sekce 2.4 v [3].
Reference [1] Cohn, P. M.: Further Algebra and Applications. Springer, 2003, ISBN 1-85233-667-6. [2] Meduna, A.: Automata and Languages: Theory and Applications. Springer, 2000, ISBN 1-85233-074-0. [3] Rozenberg, G.; Salomaa, A. (editoˇri): Handbook of Formal Languages, Vol. 1: Word, Language, Grammar, kapitola 2. Springer, 1997, ISBN 3-540-60420-0, s. 41–110. [4] Wood, D.: Theory of Computation: A Primer. Addison-Wesley Longman Publishing Co., Inc., 1987, ISBN 0-06-047208-1. ˇ ska, M.; Smrˇcka, A.; Vojnar, T.: Studijn´ı opora do pˇredmˇetu Teoretick´a informatika [online]. [5] Ceˇ Posledn´ı aktualizace 2009-11-18. [cit. 2010-07-31]. Dostupn´e na URL:
.
5
