Tähestik arvutiteaduses — definitsioon, Kleene'i sulgemine ja näited

Saa põhjalik ülevaade arvutiteaduse tähestikust, Kleene'i sulgemisest ja praktilistest näidetest — mõisted, binaar, stringid ja automaadid selgelt ja haaravalt.

Autor: Leandro Alegsa

27-09-2025 17:16

Arvutiteaduses on tähestik piiratud mittetühi hulk. Tähestiku elemente nimetatakse tähestiku tähtedeks või sümboliteks. Tavaliselt tähistatakse tähestikku suure kreeka tähega Σ {\displaystyle \Sigma } $\Sigma$ .

Näide tähestiku kohta on { - , ⋅ } {\displaystyle \{-,\cdot \}} $\{-,\cdot \}$ , mida võib kasutada morsekoodi jaoks, või {begin, if, else, for, while}, mis võivad olla programmeerimiskeele võtmesõnad. Teine tavaline näide on binaarne tähestik {0,1}, mis on aluseks arvutipõhisele kodeerimisele.

Loomulike arvude hulk ei ole tähestik, sest see ei ole lõplik (see on lõpmatu hulk). Tähestik peab olema lõplik ja mittetühi.

Arvutiteaduses kõige sagedamini kasutatav tähestik on {0,1}. Seda nimetatakse binaarseks tähestikuks, sest see sisaldab kahte sümbolit. Tähestiku tähtedest moodustatav lõplik järjestus on string (või sõna). See on tähestiku tähtede piiratud jada. Näiteks on üle tähestiku {0,1} string 01101, mille pikkus on 5.

Tühi string on string, mis ei sisalda ühtegi tähte; seda kirjutatakse sageli kujul λ {\displaystyle \lambda } $\lambda$ (sama tähistust kasutatakse mõnikord ka märgiga ε). Tühi string on string üle mis tahes tähestiku, sest see ei kasuta mingeid tähti.

Kui meil on tähestik nimega Σ {\displaystyle \Sigma } $\Sigma$ , siis kõiki sellest tähestikust moodustatavaid lõplikke stringe tähistatakse kujuga Σ ∗ {\displaystyle \Sigma ^{*}} $\Sigma ^{*}$ . Seda hulka nimetatakse Σ {\displaystyle \Sigma } Kleene'i täheks (või Kleene'i sulgemiseks). See mõiste on nime saanud matemaatiku Stephen Cole Kleene järgi.

Kleene'i sulgemine sisaldab alati tühi stringi ning kõiki erineva pikkusega sõnu. Näiteks kaheelemendilise tähestiku Kleene'i täht on { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . . } {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} $\{\lambda ,0,1,00,01,10,11,000,001,...\}$ . Kolm punkti pärast 001 näitavad, et hulk on lõpmatu ja me ei saa kõiki elemente ära loetleda.

Seotud notatsioonid ja omadused:

Σ^+ tähistab kõiki mittetühje stringe üle Σ (see on Kleene'i tähe Σ^* ilma tühi stringita).
Stringi pikkust tähistatakse tavaliselt |w|, kus w on sõna; näiteks |01101| = 5.
Kahe stringi a ja b konkateneerimine tähistatakse ab ja tähendab, et b lisatakse a lõppu.
Kui L ⊆ Σ^*, siis L nimetatakse keeleks üle tähestiku Σ — formaalne keel on lihtsalt mingi stringide hulk.

Tähestikud ja nende Kleene'i sulgemised on arvutiteaduses ja formaalsetes keeltes keskse tähtsusega: neid kasutatakse regulaaravaldiste, lõplike automaatide, grammatikateooria, keelte klassifitseerimise ning otsustusprobleemide uurimisel. Tähestike abil saab täpselt kirjeldada, millised sõnad/mõtted on genereeritavad, millised struktuurid on tuvastatavad ja millised ülesanded on arvutustehniliselt lahendatavad või lahendamatud.

Seotud leheküljed

Ametlik keel
Süntaks
Semantika

Küsimused ja vastused

K: Mis on tähestik?

V: Tähestik on sümbolite või tähtede piiratud, mitte tühi kogum.

K: Kas naturaalarvude kogumit võib pidada tähestikuks?

V: Ei, naturaalarvude kogumit ei saa pidada tähestikuks, sest see ei ole piiratud.

K: Milline on arvutiteaduses kõige sagedamini kasutatav tähestik?

V: Arvutiteaduses kõige sagedamini kasutatav tähestik on {0,1}, mida tuntakse ka kui binaarset tähestikku.

K: Mida tähendab, kui teha tähestikust string?

V: Tähestikust stringi tegemine tähendab, et sellest konkreetsest tähestikust moodustatakse piiratud tähejärjestus.

K: Mida tähendab Kleene täht?

V: Kleene'i täht viitab kõikide stringide hulgale, mida saab teha antud tähestikust, mis kirjutatakse kujul Σ∗{\displaystyle \Sigma ^{*}}. See sai oma nime matemaatiku Stephen Cole Kleene järgi.

Küsimus: Kuidas saab Kleene'i tähte esitada kahekohalise alfabeedi jaoks?

V: Kleene-tähte binaarse alfabeedi jaoks saab esitada kujul {λ, 0, 1, 00, 01, 10, 11, 000,...}. Kolm punkti pärast 001 näitavad, et seda hulka ei saa kirjutada täies mahus, sest see on lõpmatu.

Küsimus: Miks on tähestikud arvutiteaduses olulised?

V: Tähestikud on arvutiteaduses olulised, sest neid kasutatakse formaalsete keelte ja lõplike automaatide uurimisel ning keeruliste küsimuste käsitlemisel selle kohta, mida saab ja mida ei saa arvutitega arvutada.

Otsige