Aakkosto tietojenkäsittelyssä — määritelmä ja Kleenen tähti
Aakkosto tietojenkäsittelyssä — selkeä määritelmä ja Kleenen tähti: opi aakkosista, merkkijonoista, tyhjästä merkkijonosta ja Kleenen sulkeumasta käytännön esimerkein.
Tietojenkäsittelytieteessä aakkoset ovat äärellinen ei-tyhjä joukko. Aakkosten alkioita kutsutaan aakkosten kirjaimiksi tai symboleiksi. Aakkosiksi sopivat esimerkiksi merkit, numerot tai avainsanat, kunhan joukko on äärellinen ja ei-tyhjä.
Esimerkki aakkosista on { - , ⋅ }. {\displaystyle \{-,\cdot \}}
, jota voidaan käyttää morseaakkosissa, tai {begin, if, else, for, while}, jotka voivat olla ohjelmointikielen avainsanoja. Aakkoston valinta riippuu sovelluksesta: tekstiä, koodia tai signaaleja mallintavissa ongelmissa valitaan sopiva symbolijoukko.
Luonnollisten lukujen joukko ei ole aakkosto, koska se ei ole äärellinen. Käytännössä tietojenkäsittelyssä aakkoset oletetaan yleensä äärellisiksi, vaikka teoreettisissa tutkimuksissa voidaan käsitellä myös äärettömiä alkiojoukkoja.
Tietojenkäsittelytieteessä eniten käytetty aakkosto on {0,1}. Sitä kutsutaan binääriaakkosiksi, koska se sisältää kaksi symbolia. Aakkosista voidaan muodostaa merkkijono (tai sana). Tämä on äärellinen sarja aakkosten kirjaimia. Esimerkiksi merkkijono, jonka pituus on 5 {0,1}, on 01101. Merkkijonon pituus ilmaistaan usein kirjainten lukumääränä ja merkkijonon koostumus merkitään peräkkäisinä symboleina.
Tyhjä merkkijono on merkkijono, joka ei sisällä yhtään kirjainta (se kirjoitetaan usein muodossa λ {\displaystyle \lambda }
). Tyhjä merkkijono on merkkijono missä tahansa aakkosissa ja se on usein neutraali alkio merkkijonojen yhdistämisessä (konkatenoinnissa).
Aakkosten merkkijonot ja operaatiot
Jos meillä on aakkoset nimeltään Σ {\displaystyle \Sigma } 
, kirjoitetaan kaikkien niiden merkkijonojen joukon, jotka voidaan muodostaa Σ {\displaystyle \Sigma }:sta, seuraavasti: Σ ∗ {\displaystyle \Sigma ^{*}} 
. Tätä kutsutaan Σ {\displaystyle \Sigma }:n Kleenen tähdeksi (tai Kleenen sulkeutumiseksi). Se on nimetty matemaatikko Stephen Cole Kleenen mukaan.
Käytännössä Σ^{*} muodostetaan ottamalla yhteen kaikki merkkijonot, joiden pituus on mitä tahansa ei-negatiivista kokonaislukua:
- Σ^0 = { λ {\displaystyle \lambda } }
- Σ^1 = Σ
- Σ^2 = {uv | u ∈ Σ, v ∈ Σ} (kaikki kaksimerkkiäiset merkkijonot)
- Yleisesti Σ^{n} tarkoittaa kaikkia pituuden n merkkijonoja, ja Σ^{*} = \bigcup_{n\ge 0} Σ^{n}.
Otetaan myös käyttöön käsite Kleene plus, merkitty Σ^{+}, joka tarkoittaa kaikkia ei-tyhjiä merkkijonoja: Σ^{+} = \bigcup_{n\ge 1} Σ^{n} = ΣΣ^{*}.
Esimerkkejä ja ominaisuuksia
Kaksoisaakkoston Kleenen tähti on { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , . . . . } {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} 
. Kolme pistettä 001:n jälkeen osoittavat, että emme voi kirjoittaa aakkosten Kleene-tähteä kokonaisuudessaan, koska se on ääretön joukko.
Kleenen tähdellä on useita hyödyllisiä ominaisuuksia:
- Σ^{*} sisältää aina tyhjän merkkijonon λ.
- Σ^{*} on suljettu merkkijonojen yhdistämiselle (konkatenoinnille): jos u,v ∈ Σ^{*}, niin uv ∈ Σ^{*}.
- Jos Σ on äärellinen ja ei-tyhjä, niin Σ^{*} on laskettavan ääretön (countably infinite) joukko.
- Kleene-tähden laajennus koskee myös kieliä: jos L on merkkijonojoukko (kieli) yli Σ, niin L^{*} = \bigcup_{n\ge 0} L^{n} tarkoittaa kaikkia merkkijonoja, jotka saadaan kertaamalla L:n sanoja n kertaa.
Käyttö ja merkitys
Aakkoset ja niiden Kleene-tähti ovat keskeisiä käsitteitä formaalien kielten ja automaattien teoriassa sekä monissa käytännön sovelluksissa, kuten säännöllisten lausekkeiden määrittelyssä, esimerkiksi (ab)* tarkoittaa joukon kaikkia merkkijonoja, jotka koostuvat nollasta tai useammasta peräkkäisestä "ab"-toistosta. Ne ovat myös perusta kysymyksille siitä, mitä voidaan laskea ja miten kieliä tunnistaa automaateilla ja algoritmeilla (tietojenkäsittelytiede).
Lisäksi Kleenen tähteä käytetään kuvaamaan kielten sulkeutumisominaisuuksia: monet kieliluokat (esim. säännölliset kielet) ovat suljettuja Kleene-tähden ja konkatenoinnin algebrallisille operaatioille, mikä tekee niiden teoreettisesta analyysistä hallittavampaa.
Yhteenvetona: aakkosto (äärellinen, ei-tyhjä joukko) antaa rakennuspalikat, merkkijonot ovat näiden palikoiden järjestettyjä peräkkäisyyksiä, ja Kleenen tähti Σ^{*} kokoaa kaikki mahdolliset merkkijonot yhteen lukemattoman pitkään mutta laskettavasti äärettömään kokoelmaan—mikä on perusta monelle formaalin kielen ja laskennan käsitteelle.
Aiheeseen liittyvät sivut
- Virallinen kieli
- Syntaksi
- Semantiikka
Kysymyksiä ja vastauksia
Q: Mikä on aakkoset?
A: Aakkoset ovat äärellinen, ei-tyhjä joukko symboleja tai kirjaimia.
K: Voidaanko luonnollisten lukujen joukkoa pitää aakkosina?
V: Ei, luonnollisten lukujen joukkoa ei voida pitää aakkosena, koska se ei ole äärellinen.
K: Mikä on tietotekniikassa yleisimmin käytetty aakkosto?
V: Tietojenkäsittelytieteessä yleisimmin käytetyt aakkoset ovat {0,1}, joka tunnetaan myös nimellä binääriaakkoset.
K: Mitä tarkoittaa merkkijonon muodostaminen aakkosista?
V: Merkkijonon muodostaminen aakkosista tarkoittaa äärellisen kirjainsarjan luomista kyseisistä aakkosista.
K: Mitä Kleenen tähdellä tarkoitetaan?
V: Kleenen tähti tarkoittaa kaikkien niiden merkkijonojen joukkoa, jotka voidaan muodostaa tietystä aakkosesta, kirjoitettuna muodossa Σ∗{\displaystyle \Sigma ^{*}}. Se on nimetty matemaatikko Stephen Cole Kleenen mukaan.
Kysymys: Miten voimme esittää Kleenen tähden binääriselle alfabetille?
V: Kleenen tähti binäärialfabetille voidaan esittää muodossa {λ, 0, 1, 00, 01, 10, 11, 000,...}. Kolme pistettä 001:n jälkeen osoittavat, että tätä joukkoa ei voida kirjoittaa kokonaan, koska se on ääretön.
Kysymys: Miksi aakkoset ovat tärkeitä tietotekniikassa?
V: Aakkoset ovat tärkeitä tietojenkäsittelytieteessä, koska niitä käytetään tutkittaessa formaaleja kieliä ja äärellisiä automaatteja sekä pohdittaessa vaikeita kysymyksiä siitä, mitä tietokoneet voivat laskea ja mitä eivät.
Etsiä