Tähestik (arvutiteadus)

Arvutiteaduses on tähestik piiratud mittetühi hulk. Tähestiku elemente nimetatakse tähestiku tähtedeks või sümboliteks.

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.

Loomulike arvude hulk ei ole tähestik, sest see ei ole lõplik.

Arvutiteaduses kasutatakse kõige rohkem tähestikku {0,1}. Seda nimetatakse binaarseks tähestikuks, sest see sisaldab kahte sümbolit. Tähestikku saab kasutada stringi (või sõna) moodustamiseks. See on tähestiku tähtede piiratud jada. Näiteks on string pikkusega 5 üle {0,1} 01101.

Tühi string on string, mis ei sisalda ühtegi tähte (seda kirjutatakse sageli kujul λ {\displaystyle \lambda } $\lambda$ ). Tühi string on string üle mis tahes tähestiku.

Kui meil on tähestik nimega Σ {\displaystyle \Sigma } $\Sigma$ . Siis kirjutame kõigi stringide kogumi, mida saab teha Σ {\displaystyle \Sigma }, $\Sigma$ kui Σ ∗ {\displaystyle \Sigma ^{*}} $\Sigma ^{*}$ . Seda nimetatakse Σ {\displaystyle \Sigma } Kleene'i täheks (või Kleene'i sulgemiseks). $\Sigma$ . See on nimetatud matemaatiku Stephen Cole Kleene järgi.

Kaksiktä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 me ei saa tähestiku Kleene-tähte täies mahus kirjutada, sest see on lõpmatu hulk.

Tähestikud on olulised, sest neid kasutatakse formaalsete keelte, lõplike automaatide ja arvutiteaduse väga keeruliste küsimuste uurimiseks, mida saab arvutada ja mida mitte.

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.