Tähestik (matemaatika)

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 ${\displaystyle \Sigma }$  Kleene kate ehk Kleene sulund ${\displaystyle \Sigma ^{*}}$  on kõigi nende sõnede hulk, mida selle tähestiku sümbolitest saab moodustada. (Hulk ${\displaystyle \Sigma ^{\omega }}$  kõigi nende lõpmatute jadade hulk, mida selle tähestiku sümbolitest saab moodustada. Hulk ${\displaystyle \Sigma ^{\infty }}$  on hulkade ${\displaystyle \Sigma ^{*}}$  ja ${\displaystyle \Sigma ^{\omega }}$  ühend ${\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }}$ .)

Iga sõnega ${\displaystyle w}$  hulgast ${\displaystyle \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.

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 ${\displaystyle \Sigma =\{{\mathit {do}},{\mathit {re}},{\mathit {mi}}\}}$  kolme elemendiga tähestik. Nendest saab moodustada sõnesid, näiteks ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle cdfg}$ .

• 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 ${\displaystyle \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 ${\displaystyle \Sigma _{D}=\{.,-\}}$ , millest tähesageduste põhjal moodustatakse morsemärkide hulk ${\displaystyle L_{D}}$ . Peale tähtede ja numbrite on morsemärk ka SOS (${\displaystyle ...---...}$ ), milles pole pause. Märkide vahele jäetakse lühikesed pausid. See on vajalik, sest mõned märgid moodustavad ka mõne teise märgi alguse (morse ei ole prefikskood). Seega koosneb morsetähestik märkidest ja märkidevahelisest pausist: ${\displaystyle \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.

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.

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

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

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

b)  iga n ${\displaystyle \geq }$  0 korral (võib-olla tühi) n-kohaliste seosesümbolite hulk;

c)  iga n ${\displaystyle \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.

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

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.