Formella språk

Ett formellt språk är ett slags generalisering av begreppet språk, som vi känner till från vardagen.

Grundbegrepp

Till att börja med kan vi tänka oss ett formellt språk som ett vanligt språk, till exempel svenska. Vad består ett sådant språk av? Det består av ord, som vi sedan sätter ihop till meningar. Meningarna kommer inte att intressera oss, bara orden. Vad består orden av? Av bokstäver ur ett alfabet. Vi börjar därför med alfabetet.

Ett alfabet är en godtycklig icke-tom mängd. Elementen i alfabetet kallar vi symboler. När det gäller svenskan är det det vanliga svenska alfabetet med både små och stora bokstäver, inklusive å, ä och ö. Om vi i stället inte ville beskriva svenskan utan till exempel tal, skulle alfabetet innehålla alla tio siffror. Alfabetet betecknar vi ofta med symbolen Σ.

Med ett ord, eller en sträng, menar vi en ändlig följd av symboler ur ett alfabet Σ. Om vi till exempel har alfabetet Σ= {a,b,c,d,e,…, z}, är ett ord till exempel följden ”hej” eller ”hund”, men inte ”kväll” (där finns inte bokstaven ”ä”), ”Hugo” (där finns inte bokstaven ”H”) eller ”god dag” (där finns inget mellanslag). Med ordets längd menar vi antalet symboler som ordet består av.

Konkatenering av ord: om vi har två ord a = a₁a₂… a_n och b = b₁b₂… b_m, får vi genom konkatenering av orden ordet ab = a₁a₂… a_nb₁b₂… b_m. Exempel: konkatenering av orden ”hej” och ”hund” ger ordet ”hejhund”. Konkatenering betecknar vi antingen med ringoperatorn, dvs. a ∘ b, eller inte alls, och då skriver vi helt enkelt skriver orden efter varandra utan någon särskild symbol för konkatenering.

Det tomma ordet betecknar vi ε, och det är det ord som har längden noll. Om vi konkatenerar ett ord a = a₁… a_n med det tomma ordet ε, får vi tillbaka ordet a. Alltså gäller a ∘ ε = a.

Kleenestjärnan av alfabetet Σ är mängden av alla ord som vi kan bilda med alfabetet Σ, inklusive det tomma ordet. Kleenestjärnan betecknar vi Σ^∗. Om vi har det binära alfabetet Σ= {0, 1}, gäller

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

Ibland använder vi också alfabetets Kleeneplus, som återigen består av alla ord vi kan bilda med alfabetet, utom det tomma ordet. Kleeneplus betecknar vi Σ⁺, och det gäller att Σ⁺ = Σ^∗ ∖ {ε}.

Exempel på alfabet

• Vi går tillbaka till exemplet med svenskan. Varje svenskt ord finns i Kleenestjärnan av det alfabet som innehåller små och stora bokstäver och varianter med å, ä och ö (och kanske ett bindestreck ”-”). Om vi till detta alfabet lägger till mellanslag och skiljetecken (komma, punkt, utropstecken, frågetecken, …), får vi i Kleenestjärnan alla meningar som vi kan bilda på svenska. Till Kleenestjärnan hör förstås också meningar av typen ”sadflsf kasdf kagrjewåäöker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, som ändå är begripligare än en del kommentarsfält på nätet.

• Om vårt alfabet innehåller alla siffror Σ= {0, 1, …, 9}, finns alla positiva heltal i Kleenestjärnan — och några till. Där finns nämligen också tal som börjar med noll, till exempel 00054, eller bara nollan, och dessutom det tomma ordet, som förstås inte är något tal alls.

• Ett alfabet måste vara icke-tomt, så det minsta alfabetet har minst en symbol. För alfabetet Σ= {!} får vi till exempel Kleenestjärnan Σ^∗ = {ε, !, !!, !!!, !!!!, …}, dvs. en mängd av ord, där det för varje n ∈ ℕ finns ett ord med n utropstecken i Kleenestjärnan, och inga andra ord finns där.

• Låt Σ= {qw,c}. Det här är ett mycket märkligt alfabet, eftersom det innehåller ordet qw. Den här beteckningen används vanligtvis inte, eftersom den är förvirrande och konstig, men vi kan tänka oss att vi klistrar ihop bokstäverna ”q” och ”w” så att de bildar ett enda tecken. Då kan vi se ordet ”qw” som symbolen ”qw”. Om vi av den här symbolen bildade ordet ”qwcqw”, skulle ordet ha längden tre — det skulle bestå av symbolerna ”qw”, ”c” och ”qw”. Så här märkliga alfabet träffar vi inte på så ofta, men det finns situationer där vi behöver använda symboler som består av flera symboler.

Formellt språk

Ett (formellt) språk över alfabetet Σ är en godtycklig delmängd av Σ^∗. För ett språk L över alfabetet Σ gäller alltså L ⊆ Σ^∗. Exempel på språk:

• I föregående avsnitt definierade vi alfabetet av siffror Σ= {0, 1, …, 9}. Kleenestjärnan består av alla ord som bara består av siffror. Om vi lägger till regeln att ordet inte får börja med noll och inte får vara tomt, får vi mängden av de positiva heltalen ℤ⁺. Det gäller att ℤ⁺ ⊆ Σ^∗, så ℤ⁺ är ett språk över alfabetet Σ.

• Till den föregående mängden av siffror kan vi lägga till tecknet minus ”-”, så att Σ= {0, 1, …, 9, −}. Kleenestjärnan består av alla ord som består av siffror eller minustecken. Det betyder dock att Kleenestjärnan också innehåller ord som ”12-84-”, ”1-5-8” eller ”-”. Språket av heltalen ℤ skapar vi genom att lägga till tre regler:

  • Minustecknet förekommer inte alls i ordet eller förekommer i början av ordet.
  • Den första siffran i ordet får inte vara noll, utom i ordet ”0”.
  • Varje ord måste innehålla minst en siffra.

  Den här mängden beskriver mängden av heltal och är en delmängd av mängden Σ^∗ — det är alltså ett språk över alfabetet Σ.

• Låt Σ= {0, 1}. Kleenestjärnan består alltså av alla ord som består av nollor och ettor. Ett språk L över det här alfabetet kan vi till exempel definiera som mängden av alla ord som har exakt tre ettor. Vi kan också vara mer kreativa och säga att språket L är mängden av alla ord som utgör en giltig docx-fil (det som kommer ut ur Word).

• Vi håller oss till det binära alfabetet Σ= {0, 1}. Varje sträng av tecken (vanliga tecken som finns på tangentbordet) kan översättas till binär form, dvs. till nollor och ettor, och tillbaka igen, till exempel med hjälp av ASCII-tabellen (eller mer exakt — ASCII-tabellen översätter tecken till tal och tal i det decimala talsystemet kan översättas till tal i det binära talsystemet). Vi kan alltså definiera språket av alla ord som motsvarar en giltig e-postadress, och det är fortfarande ett språk över det binära alfabetet.

Konkatenering av språk: vi kan konkatenera även språk. Definitionen är ungefär som för den kartesiska produkten av mängder. Låt oss ta två språk L₁ och L₂. Genom att konkatenera dem, L₁ ∘ L₂, får vi ett nytt språk, som vi definierar så här:

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

Dvs. vi tar alla ord ur språket L₁ och konkatenerar dem med alla ord ur språket L₂. Exempel: låt

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

Då gäller:

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

Hittills har vi beskrivit språk med vanligt språk, vi har helt enkelt med ord beskrivit hur språket ska se ut. Det är dock mycket opraktiskt, så man inför ett mer formellt sätt att definiera ett språk. Det första av dem är grammatiken.