Formaalit kielet

Formaali kieli on eräänlainen yleistys arkielämästä tutusta kielen käsitteestä.

Peruskäsitteet

Formaalin kielen voi aluksi kuvitella tavalliseksi kieleksi, vaikkapa suomeksi. Mistä tällainen kieli koostuu? Se koostuu sanoista, jotka yhdistämme edelleen lauseiksi. Lauseet eivät meitä kiinnosta, vain sanat. Mistä sanat koostuvat? Aakkoston kirjaimista. Aloitamme siis aakkostosta.

Aakkosto on mikä tahansa epätyhjä joukko. Aakkoston alkioita kutsutaan symboleiksi. Jos puhutaan suomen kielestä, aakkosto on tavallinen suomen aakkosto, jossa on sekä pienet että isot kirjaimet. Jos haluaisimme kuvata kielen sijaan vaikkapa lukuja, aakkostossa olisi kaikki kymmenen numeroa. Aakkostoa merkitään usein symbolilla Σ.

Sanalla, eli myös merkkijonolla, tarkoitetaan jonkin aakkoston Σ symbolien äärellistä jonoa. Jos meillä on esimerkiksi aakkosto Σ= {a,b,c,d,e,…, z}, sana on esimerkiksi jono ”moi” tai ”dobermanni”, mutta ei enää ”yö” (aakkostossa ei ole kirjainta ”ö”), ”Pekka” (aakkostossa ei ole kirjainta ”P”) eikä ”hyvää päivää” (aakkostossa ei ole kirjainta ”ä” eikä välilyöntiä). Sanan pituudella tarkoitetaan niiden symbolien lukumäärää, joista sana koostuu.

Sanojen konkatenaatio eli liittäminen: jos meillä on kaksi sanaa a = a₁a₂… a_n ja b = b₁b₂… b_m, sanojen liittämisestä syntyy sana ab = a₁a₂… a_nb₁b₂… b_m. Esimerkki: sanoista ”moi” ja ”dobermanni” syntyy liittämällä sana ”moidobermanni”. Konkatenaatiota merkitään joko rengasoperaattorilla, eli a ∘ b, tai sitä ei merkitä lainkaan, vaan sanat kirjoitetaan peräkkäin ilman erityistä liittämismerkkiä.

Tyhjää sanaa merkitään ε, ja se on sana, jonka pituus on nolla. Jos liitämme sanaan a = a₁… a_n tyhjän sanan ε, saamme takaisin sanan a. Siis a ∘ ε = a.

Aakkoston Σ sulkeuma (Kleenen tähti) on kaikkien niiden sanojen joukko, jotka voimme muodostaa aakkostosta Σ, tyhjä sana mukaan lukien. Sulkeumaa merkitään Σ^∗. Jos meillä on binääriaakkosto Σ= {0, 1}, niin

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Joskus käytetään myös aakkoston positiivista sulkeumaa, johon kuuluvat taas kaikki aakkostosta muodostettavissa olevat sanat tyhjää sanaa lukuun ottamatta. Positiivista sulkeumaa merkitään Σ⁺, ja Σ⁺ = Σ^∗ ∖ {ε}.

Esimerkkejä aakkostoista

• Palataan suomen kielen esimerkkiin. Jokainen suomen kielen sana löytyy sellaisen aakkoston sulkeumasta, joka sisältää pienet ja isot kirjaimet sekä ääkköset (ja ehkä vielä yhdysmerkin ”-”). Jos tähän aakkostoon lisätään vielä välilyönti ja välimerkit (pilkku, piste, huutomerkki, kysymysmerkki, …), sulkeumasta löytyvät kaikki lauseet, jotka suomen kielellä voi muodostaa. Sulkeumaan kuuluvat tietenkin myös sellaiset ”lauseet” kuin ”sadflsf kasdf kagrjewiäöåker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, joilla ei ole mitään merkitystä.

• Jos aakkostossamme on kaikki numerot Σ= {0, 1, …, 9}, sulkeumassa ovat kaikki positiiviset kokonaisluvut — ja vähän muutakin. Mukana on nimittäin myös nollalla alkavia lukuja, esimerkiksi 00054, sekä pelkkä nolla, ja lisäksi tyhjä sana, joka ei tietenkään ole mikään luku.

• Aakkoston täytyy olla epätyhjä, joten pienimmässä aakkostossa on vähintään yksi symboli. Aakkostosta Σ= {!} saisimme sulkeuman Σ^∗ = {ε, !, !!, !!!, !!!!, …}, eli sanojen joukon, jossa jokaista lukua n ∈ ℕ kohti on sana, jossa on n huutomerkkiä, eikä sulkeumassa ole muita sanoja.

• Olkoon Σ= {qw,c}. Tämä on hyvin erikoinen aakkosto, koska se sisältää sanan qw. Tällaista merkintää ei yleensä käytetä, koska se on sekava ja outo, mutta sen voi kuvitella niin, että kirjaimet ”q” ja ”w” liimataan yhteen ja ne muodostavat yhden merkin. Silloin voimme nähdä sanan ”qw” symbolina ”qw”. Jos tästä symbolista muodostettaisiin sana ”qwcqw”, sen pituus olisi kolme — se koostuisi symboleista ”qw”, ”c” ja ”qw”. Tällaisia aakkostoja ei kohdata kovin usein, mutta on tilanteita, joissa tarvitaan useasta merkistä koostuvia symboleja.

Formaali kieli

(Formaali) kieli aakkoston Σ yllä on mikä tahansa joukon Σ^∗ osajoukko. Aakkoston Σ yllä olevalle kielelle L siis pätee L ⊆ Σ^∗. Esimerkkejä kielistä:

• Edellisessä osassa määrittelimme numeroaakkoston Σ= {0, 1, …, 9}. Sulkeumassa ovat kaikki pelkistä numeroista muodostetut sanat. Jos lisäämme säännön, että sana ei saa alkaa nollalla eikä se saa olla tyhjä, saamme positiivisten kokonaislukujen joukon ℤ⁺. Pätee ℤ⁺ ⊆ Σ^∗, joten ℤ⁺ on kieli aakkoston Σ yllä.

• Edelliseen numeroiden joukkoon voimme lisätä vielä miinusmerkin ”-”, jolloin Σ= {0, 1, …, 9, −}. Sulkeumassa ovat kaikki sanat, jotka koostuvat numeroista tai miinusmerkistä. Se tarkoittaa kuitenkin sitä, että sulkeumassa on myös sanoja kuten ”12-84-”, ”1-5-8” tai ”-”. Kokonaislukujen kielen ℤ saamme lisäämällä kolme sääntöä:

  • Miinusmerkki ei esiinny sanassa lainkaan tai se esiintyy sanan alussa.
  • Sanan ensimmäinen numero ei voi olla nolla paitsi sanassa ”0”.
  • Jokaisessa sanassa on oltava vähintään yksi numero.

  Tämä joukko kuvaa kokonaislukujen joukkoa ja on joukon Σ^∗ osajoukko — se on siis kieli aakkoston Σ yllä.

• Olkoon Σ= {0, 1}. Sulkeuman muodostavat silloin kaikki sanat, jotka koostuvat nollista ja ykkösistä. Kielen L tämän aakkoston yllä voimme määritellä vaikkapa kaikkien sellaisten sanojen joukoksi, joissa on täsmälleen kolme ykköstä. Voimme olla luovempiakin ja sanoa, että kieli L on kaikkien sellaisten sanojen joukko, jotka ovat kelvollisia docx-tiedostoja (sellaisia, joita Word tallentaa).

• Pysytään binääriaakkostossa Σ= {0, 1}. Jokaisen merkkijonon (tavallisten merkkien, joita näppäimistössä on) voi muuttaa binäärimuotoon, eli nolliksi ja ykkösiksi, ja takaisin esimerkiksi ASCII-taulukon avulla (tai tarkemmin — ASCII-taulukko muuttaa merkit luvuiksi ja kymmenjärjestelmän luvut voi muuttaa kaksijärjestelmän luvuiksi). Voimme siis määritellä kielen, joka koostuu kaikista kelvollista sähköpostiosoitetta vastaavista sanoista, ja se on edelleen kieli binääriaakkoston yllä.

Kielten konkatenaatio: myös kieliä voi liittää yhteen. Määritelmä on samankaltainen kuin joukkojen karteesisella tulolla. Olkoon meillä kaksi kieltä L₁ ja L₂. Niiden konkatenaatiolla L₁ ∘ L₂ saadaan uusi kieli, jonka määrittelemme näin:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Eli otamme kaikki kielen L₁ sanat ja liitämme ne kaikkiin kielen L₂ sanoihin. Esimerkki: olkoon

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,moi\}\end{array}$$

Silloin pätee:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0moi,1a,1b,1moi\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,moi0,moi1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Tähän asti olemme kuvanneet kieliä tavallisella kielellä, eli olemme sanallisesti kuvailleet, millainen kielen pitäisi olla. Se on kuitenkin hyvin epäkäytännöllistä, joten otetaan käyttöön muodollisempi tapa määritellä kieli. Ensimmäinen niistä on kielioppi.