Tähestik (matemaatika)

Matemaatikas (matemaatilises loogikas, formaalsete keelte teoorias, automaaditeoorias, poolautomaaditeoorias) ja informaatikas nimetatakse tähestikuks omavahel erinevate sümbolite ehk märkide ehk tähtede lõplikku hulka.

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.^[1] Neist võetakse märgid sõnade moodustamiseks ja nii on need formaalsete keelte aluseks. Tuleb eristada üksikmärkidest koosnevat tähestikku ja mitmesuguse pikkusega sõnu, mida selle tähestiku abil saab moodustada. ^[2]

Definitsioon

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.^[3]^[4]

Viited

↑ 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õnades 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.

[1] 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õnades 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$ ).

[2] 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.

[3] {{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.

[4] 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.

[1]

[2]

[3]

[4]