Tähestik (matemaatika)

Matemaatikas (matemaatilises loogikas, formaalsete keelte teoorias, automaaditeoorias, poolautomaaditeoorias), informaatikas (teoreetilises informaatikas) ning lingvistikas nimetatakse tähestikuks omavahel erinevate sümbolite ehk märkide ehk tähtede lõplikku hulka^[1] või mittetühja lõplikku hulka^[2]^[3]^[4], mõnikord ka mis tahes võimsusega hulka, olgu siis lõplikku hulka (näiteks mõne loomuliku keele tähestikku), loenduvat hulka või mitteloenduvat hulka. Kõige sagedamini koosneb see tähtedest või ASCII-keelemärkidest. Need on tavaliselt mõeldud tähistama tähti, numbreid, foneeme või sõnu.

Tähestikke tähistatakse sageli tähega $\Sigma$ (sigma), harvem tähega $V$ (inglise sõnast vocabulary, mis tähendab siinses mõttes tähestikku.^[5] Neist võetakse märgid sõnede moodustamiseks ja nii on need formaalsete keelte aluseks. Tuleb eristada üksikmärkidest koosnevat tähestikku ja mitmesuguse pikkusega sõnesid, mida selle tähestiku abil saab moodustada.^[6]

Definitsioon[muuda | muuda lähteteksti]

Tähestik on lõplik hulk. Sageli nõutakse ka, et see hulk ei oleks tühi. Tähestiku elemente nimetatakse tähtedeks, sümboliteks või märkideks.^[7]^[8]^[9]^[10] Niiviisi defineerituna on tähestik märkide varu, sama mis märgikomplekt.^[11]

Sõne on tähestiku sümbolite lõplik jada. Tähestiku $\Sigma$ Kleene kate ehk Kleene sulund $\Sigma ^{*}$ on kõigi nende sõnede hulk, mida selle tähestiku sümbolitest saab moodustada. (Hulk $\Sigma ^{\omega }$ kõigi nende lõpmatute jadade hulk, mida selle tähestiku sümbolitest saab moodustada. Hulk $\Sigma ^{\infty }$ on hulkade $\Sigma ^{*}$ ja $\Sigma ^{\omega }$ ühend $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ .)

Iga sõnega $w$ hulgast $\Sigma ^{*}$ üheselt määratud arvu, mis on sõne kui lõpliku jada pikkus, nimetatakse selle sõne pikkuseks.

Tehted sõnedega on konkatenatsioon, astendamine (mitmekordselt järjestikku asetamine), peegeldus.

Erinevus loomulikust keelest[muuda | muuda lähteteksti]

Tähestik matemaatikas ja informaatikas on loomulikes keeltes kasutatavate tavaliste tähestike üldistus. Näiteks moodustavad ladina tähed ka selles üldistatud tähenduses tähestiku. Ent teoreetilises informaatikas esineb sageli ka tähestikke, mille sümboleid esitatakse mitmest tähest koosnevana. Näiteks on $\Sigma =\{{\mathit {do}},{\mathit {re}},{\mathit {mi}}\}$ kolme elemendiga tähestik. Nendest saab moodustada sõnesid, näiteks $\color {black}{\mathit {do}}\color {red}{\mathit {mi}}\color {black}{\mathit {do}}\color {red}{\mathit {re}}$ .

Siin avaldub sümbolite arbitraarsus: ei ole põhimõtteliselt tähtis, milliseid märke tähestiku elementidena kasutatakse, peaasi et nad oleksid üksteisest eristatavad. Näiteks võib märgiahel $\color {black}{\mathit {do}}\color {red}{\mathit {mi}}\color {black}{\mathit {do}}\color {red}{\mathit {re}}$ tähistada helijärjendit, kuid samahästi ka kolme järjestikust käsku.

Matemaatikas ja informaatikas nimetatakse sõneks tähestiku märkide mis tahes järjendit, näiteks ka $cdfg$ .

Näiteid[muuda | muuda lähteteksti]

Kõige tavalisem tähestiku näide on kahendtähestik {0,1}. Sõned üle selle tähestiku on näiteks 101, 001101 ja 11100010101.
Sagedane näide on ka inglise tähestik. Näideteks sobivad ka näiteks eesti tähestik, kreeka tähestik {α, β, ... , ψ, ω} ja itaalia tähestik {a, b, c, d, e, f, g, h, i, l, m, n, o, p, q, r , s, t, u, v, z}.
Tähestiku $\Sigma =\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace$ abil saab esitada kõiki naturaalarve kümnendsüsteemis. Tähtede ja sõnede eristusele vastab numbrite ehk numbrimärkide ja numbrite ehk arvuesituste eristus. Arv on siis abstraktsioon, nimelt süntaktiliselt korrektse arvuesituse osutus.
Rooma numbrite süsteem põhineb aluskujul tähestikul Σ = {I, V, X, L, C, D, M} (suurte arvude jaoks on olemas mitmesugused laiendused). Siin on reeglid, mida märgijadad peavad järgima, et olla selle süsteemi sõned, keerulised (mitte IIII, vaid IV; suuremad ühikud kaugemal vasakul kui väiksemad jne). Neid saab esitada formaalse grammatika abil. Märgijadad 13 ja XIII on ühe ja sellesama arvu esitused.
Morset saab esitada kahe erineva tähestiku abil, mis kirjeldavad morse kommunikatsioonisüsteemi eri tasanditel. Esimene on tähestik $\Sigma _{D}=\{.,-\}$ , millest tähesageduste põhjal moodustatakse morsemärkide hulk $L_{D}$ . Peale tähtede ja numbrite on morsemärk ka SOS ( $...---...$ ), milles pole pause. Märkide vahele jäetakse lühikesed pausid. See on vajalik, sest mõned märgid moodutavad ka mõne teise märgi alguse (morse ei ole prefikskood). Seega koosneb morsetähestik märkidest ja märkidevahelisest pausist: $\Sigma _{M}=L_{D}\cup \{{\text{PAUS}}\}$ .

Viimasest näitest on näha, et keeruka kommunikatsiooni ehitust saab mõnikord kirjeldada tähestike ja keelte hierarhilise paari abil.

Esimest järku loogika tähestik[muuda | muuda lähteteksti]

Mingi loogika keskne koostisosa on selle aluseks olev keel. Selle keele tähestik annab nende märkide hulga, mida saab selle loogika termide ja valemite ehitamiseks kasutada.

Ühe esimest järku loogika tähestiku definitsioon[muuda | muuda lähteteksti]

Mingi esimest järku loogika tähestik hõlmab järgmised märgid:^[12]

$v_{0},v_{1},v_{2},\ldots \ -$ muutujad;
$\neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow \ -$ konnektorid, mis tähistavad eitust, konjunktsiooni, disjunktsiooni, implikatsiooni, ekvivalentsi;
$\forall ,\exists \ -$ üldisuskvantor ja olemasolukvantor;
$\equiv \ -$ võrdusmärk;
$),(,{\boldsymbol {,}}\ -$ tehnilised märgid: sulud ja koma;
peale selle

a) (võib-olla tühi) indiviidikonstantide hulk;

b) iga n

\geq

0 korral (võib-olla tühi) n-kohaliste seosesümbolite hulk;

c) iga n

\geq

0 korral (võib-olla tühi) n-kohaliste funktsioonisümbolite hulk.

Olgu A (1) kuni (5) all loetletud sümbolite hulk ning S (6) all loetletud sümbolite hulka. Tähistagu A_S hulkade A ja S ühendit. Hulka A_S nimetatakse esimest järku loogika tähestikuks ja hulka S selle hulga sümbolihulgaks. Selleks et anda esimest järku predikaatloogika, on piisav anda tema sümbolihulk.

Mõnikord loobutakse tähestikus võrdusmärgist. Sellisel juhul peab sümbolihulk sisaldama vähemalt ühte seosesümbolit, sest muidu ei saa valemeid moodustada.

Näide[muuda | muuda lähteteksti]

Tähtsaim esimest järku loogika, hulgateooria keel, sisaldab oma tähestiku sümbolihulgas ainult ühte kahekohalist seosesümbolit $\in$ , mis tähistab kuuluvusseost (vt Hulk).

Rakendused[muuda | muuda lähteteksti]

Tähestikud on olulised formaalsete keelte, automaatide ja poolautomaatide kontekstis. Automaatide, näiteks deterministlike lõplike automaatide defineerimisel on tarvis määrata tähestik, millest ehitatakse automaadi sisendsõned. Nendes rakendustes nõutakse tavaliselt, et tähestik oleks lõplik hulk.

Kui automaate, regulaaravaldisi või formaalseid grammatikaid kasutatakse sõnetöötluse algoritmide osana, siis võidakse eeldada, et tähestik on nende algoritmidega töödeldavate tekstide tähekomplekt või selle alamhulk, mis koosneb lubatavatest tähtedest.

Viited[muuda | muuda lähteteksti]

↑ Alfred V. Aho, Ravi Sethi, Jeffrey Ullman. Compilers: Principles, Techniques, and Tools, Addison-Wesley 1985, ISBN 0-201-10088-6, lk 92: "The term alphabet or character class denotes any finite set of symbols."
↑ H.-D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic, 2. trükk, Springer: New York 1984, ISBN 0-387-94258-0, lk 11: "By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols."
↑ Peter Fletcher, Hughes Hoyle, C. Wayne Patty, Foundations of Discrete Mathematics, PWS-Kent 1991. ISBN 0-53492-373-9, lk 114: "An alphabet is a nonempty finite set the members of which are called symbols or characters."
↑ Kenneth H. Rosen. Discrete Mathematics and Its Applications, 7. trükk, McGraw-Hill 2012, lk 849: "A vocabulary (or alphabet) V is a finite, nonempty set of elements called symbols."
↑ Formaalse grammatika $G$ ning selle genereeritud formaalse keele $L(G)$ kontekstis nimetatakse formaalse keele märgistikku terminaltähestikuks ehk terminaalseks tähestikuks ning tähistatakse sageli ( $\Sigma$ asemel) tähega $T$ . Peale selle vajab formaalne grammatika veel terminaltähestikuga ühisosata mittetühja mitteterminalide ehk muutujate hulka, mida sageli tähistatakse tähega $N$ (harvem tähega $V$ ), formaalselt on seejuures samuti tegu tähestikuga. Mitteterminalid ei tohi keele $L(G)$ [[sõne (informaatika)|]]des esineda. Terminalide hulga ja mitteterminalide hulga (ühisosata) ühend on siis kogu tähestik ehk "vokabulaar", mida tähistatakse sageli tähega $V$ (või ka $\Sigma$ ).
↑ Christian Wagenknecht, Michael Hielscher. Formale Sprachen, abstrakte Automaten und Compiler: Lehr- und Arbeitsbuch für Grundstudium und Fortbildung, ISBN 3-8348-0624-2, lk 20.
↑ Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung, 2. täiendatud trükk, Springer-Verlag 2002, ISBN=3-540-42624-8, lk 27.
↑ Juraj Hromkovič. Theoretische Informatik: Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie, B.G. Teubner Verlag 2004, ISBN=3-519-10332-X, lk 33.
↑ Susanna S. Epps. Discrete Mathematics with Applications, 4. trükk, Brooks Cole Pub Co 2010, ISBN=0-495-39132-8, lk 781.
↑ Alexandru Mateescu, Arto Salomaa. Formal Languages: an Introduction and a Synopsis. – Grzegorz Rozenberg, Arto Salomaa (toim). Handbook of Formal Languages, Word, Language, Grammar', kd 1, Springer-Verlag 1997, ISBN=3-540-60420-0, lk 10.
↑ Manfred Broy. Systemstrukturen und Theoretische Informatik, Informatik: Eine grundlegende Einführung, kd 2, 2., ümbertöötatud trükk, Springer: Berlin 1998, ISBN=3-540-64392-3, lk 191.
↑ Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas. Einführung in die mathematische Logik, Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4, lk 13.

Välislingid[muuda | muuda lähteteksti]

[aho-1] Alfred V. Aho, Ravi Sethi, Jeffrey Ullman. Compilers: Principles, Techniques, and Tools, Addison-Wesley 1985, ISBN 0-201-10088-6, lk 92: "The term alphabet or character class denotes any finite set of symbols."

[ebbinghaus-2] H.-D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic, 2. trükk, Springer: New York 1984, ISBN 0-387-94258-0, lk 11: "By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols."

[3] Peter Fletcher, Hughes Hoyle, C. Wayne Patty, Foundations of Discrete Mathematics, PWS-Kent 1991. ISBN 0-53492-373-9, lk 114: "An alphabet is a nonempty finite set the members of which are called symbols or characters."

[4] Kenneth H. Rosen. Discrete Mathematics and Its Applications, 7. trükk, McGraw-Hill 2012, lk 849: "A vocabulary (or alphabet) V is a finite, nonempty set of elements called symbols."

[5] Formaalse grammatika $G$ ning selle genereeritud formaalse keele $L(G)$ kontekstis nimetatakse formaalse keele märgistikku terminaltähestikuks ehk terminaalseks tähestikuks ning tähistatakse sageli ( $\Sigma$ asemel) tähega $T$ . Peale selle vajab formaalne grammatika veel terminaltähestikuga ühisosata mittetühja mitteterminalide ehk muutujate hulka, mida sageli tähistatakse tähega $N$ (harvem tähega $V$ ), formaalselt on seejuures samuti tegu tähestikuga. Mitteterminalid ei tohi keele $L(G)$ [[sõne (informaatika)|]]des esineda. Terminalide hulga ja mitteterminalide hulga (ühisosata) ühend on siis kogu tähestik ehk "vokabulaar", mida tähistatakse sageli tähega $V$ (või ka $\Sigma$ ).

[6] Christian Wagenknecht, Michael Hielscher. Formale Sprachen, abstrakte Automaten und Compiler: Lehr- und Arbeitsbuch für Grundstudium und Fortbildung, ISBN 3-8348-0624-2, lk 20.

[7] Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung, 2. täiendatud trükk, Springer-Verlag 2002, ISBN=3-540-42624-8, lk 27.

[8] Juraj Hromkovič. Theoretische Informatik: Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie, B.G. Teubner Verlag 2004, ISBN=3-519-10332-X, lk 33.

[9] Susanna S. Epps. Discrete Mathematics with Applications, 4. trükk, Brooks Cole Pub Co 2010, ISBN=0-495-39132-8, lk 781.

[10] Alexandru Mateescu, Arto Salomaa. Formal Languages: an Introduction and a Synopsis. – Grzegorz Rozenberg, Arto Salomaa (toim). Handbook of Formal Languages, Word, Language, Grammar', kd 1, Springer-Verlag 1997, ISBN=3-540-60420-0, lk 10.

[11] Manfred Broy. Systemstrukturen und Theoretische Informatik, Informatik: Eine grundlegende Einführung, kd 2, 2., ümbertöötatud trükk, Springer: Berlin 1998, ISBN=3-540-64392-3, lk 191.

[12] Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas. Einführung in die mathematische Logik, Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4, lk 13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]