Symbolijoukkoja

Symbolijoukkoja on joukko symboleita, joita käytetään muodostamaan merkkijonoja formalistisissa kieliopissa kuten automaatioteoriassa, kieliteoriassa ja koodauksessa. Symbolijoukko (monikossa symbolijoukkoja) tunnetaan myös nimellä alfabeetti. Usein symbolijoukko on finite, mutta se voi olla myös äärellisen tai äärettömän kokoinen.

Merkkijonot muodostetaan näiden symbolien sekvensseinä. Mikä tahansa merkkijono, jonka jokainen merkki kuuluu tiettyyn symbolijoukkoon Σ, on merkkijono Σ*:n eli kaikkien mahdollisten merkkijonojen joukko. Tyhjä merkkijono ε kuuluu Σ*:hin ja sen pituus on 0. Esimerkiksi Σ = {0,1} tuottaa kaikki binäärijonot; Σ* sisältää ε:n sekä kaikkien pituuksien jekejä kuten 0, 1, 00, 01, 10, 11, 000, jne.

Symbolijoukkoja voidaan yhdistää ja muokata vähän kuin sanoja kielissä. Yleisimmät operatiot ovat yhdiste (Σ1 ∪ Σ2) ja leikkaus (Σ1 ∩ Σ2), jotka muodostavat uuden symbolijoukon, joka koostuu kummassakin tapauksessa molempien joukkojen merkeistä. Symbolijoukkoja voidaan käsitellä suhteessa niihin muodostettuihin kieliin: kieli over Σ on minkä tahansa Σ*-osajoukko, ja usein puhutaan kielen sanakirjasta sekä sen ominaisuuksista kuten säännöllisyys, kontekstuaalinen riippuvuus tai kontekstivapaa rakenne.

Symbolijoukkoja käytetään laajasti automaattien, säännöllisten lausekkeiden, Grammatikoiden ja koodausmenetelmien määrittelyssä sekä ohjelmoinnissa, jossa erilaiset merkkijonot ratkaisevat ohjelman käyttäytymisen.