Formelle språk

Et formelt språk er en slags generalisering av språkbegrepet vi kjenner fra hverdagen.

Grunnbegreper

Til å begynne med kan vi tenke på et formelt språk som et vanlig språk, for eksempel norsk. Hva består et slikt språk av? Det består av ord, som vi videre setter sammen til setninger. Setningene kommer vi ikke til å bry oss om, bare ordene. Hva består ordene av? Av bokstaver i et alfabet. Derfor begynner vi med alfabetet.

Et alfabet er en vilkårlig mengde som ikke er tom. Elementene i alfabetet kaller vi symboler. For norsk er det det vanlige norske alfabetet med både små og store bokstaver, inkludert æ, ø og å. Hvis vi ikke ville beskrive norsk, men for eksempel tall, ville alfabetet inneholdt alle ti sifrene. Alfabetet betegner vi ofte med symbolet Σ.

Med et ord, eller en streng, mener vi en endelig følge av symboler fra et alfabet Σ. Hvis vi for eksempel har alfabetet Σ= {a,b,c,d,e,…, z}, er følgen «hei» eller «dobermann» et ord, men ikke «blåbær» (vi har ikke bokstavene «å» og «æ»), «Hans» (vi har ikke bokstaven «H») eller «god dag» (vi har ikke mellomrom). Med lengden til et ord mener vi antallet symboler ordet består av.

Sammenkobling av ord: hvis vi har to ord a = a₁a₂… a_n og b = b₁b₂… b_m, får vi ved å koble dem sammen ordet ab = a₁a₂… a_nb₁b₂… b_m. Eksempel: hvis vi kobler sammen ordene «hei» og «dobermann», får vi ordet «heidobermann». Sammenkoblingen betegner vi enten med en ring, altså a ∘ b, eller vi bruker ikke noe tegn og skriver bare ordene etter hverandre uten et spesielt symbol for sammenkobling.

Det tomme ordet betegner vi med ε, og det er ordet som har lengde null. Hvis vi kobler ordet a = a₁… a_n sammen med det tomme ordet ε, får vi ordet a tilbake. Altså gjelder a ∘ ε = a.

Kleene-stjernen av alfabetet Σ er mengden av alle ord vi kan lage av alfabetet Σ, inkludert det tomme ordet. Kleene-stjernen betegner vi Σ^∗. Hvis vi har det binære alfabetet Σ= {0, 1}, gjelder

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

Av og til bruker vi også Kleene-pluss av alfabetet. Det er igjen alle ordene vi kan sette sammen av alfabetet, bortsett fra det tomme ordet. Kleene-pluss betegner vi Σ⁺, og det gjelder Σ⁺ = Σ^∗ ∖ {ε}.

Eksempler på alfabeter

• Vi går tilbake til eksempelet med norsk. Hvert norsk ord finner vi i Kleene-stjernen av et alfabet som inneholder små og store bokstaver (pluss kanskje bindestrek «-»). Hvis vi legger til mellomrom og tegnsetting (komma, punktum, utropstegn, spørsmålstegn, …) til dette alfabetet, får vi i Kleene-stjernen alle setninger vi kan lage på norsk. Kleene-stjernen vil selvfølgelig også inneholde setninger som «sadflsf kasdf kagrjewæøåiåkør kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf», som ikke har noen mening i det hele tatt.

• Hvis alfabetet vårt inneholder alle sifrene Σ= {0, 1, …, 9}, vil Kleene-stjernen inneholde alle naturlige tall — og noen til. Der finnes nemlig også tall som begynner med null, for eksempel 00054, eller bare null, og dessuten finnes det tomme ordet, som selvfølgelig ikke er noe tall.

• Alfabetet må ikke være tomt, så det minste alfabetet har minst ett symbol. For alfabetet Σ= {!} får vi for eksempel Kleene-stjernen Σ^∗ = {ε, !, !!, !!!, !!!!, …}, altså en mengde ord der det for hvert n ∈ ℕ₀ finnes et ord med n utropstegn, og ingen andre ord finnes i Kleene-stjernen.

• La Σ= {qw,c}. Dette er et veldig spesielt alfabet, fordi det inneholder ordet qw. Denne skrivemåten brukes vanligvis ikke, fordi den er forvirrende og rar, men vi kan tenke oss at vi limer bokstavene «q» og «w» sammen slik at de danner ett tegn. Da kan vi se ordet «qw» som symbolet «qw». Hvis vi lager ordet «qwcqw» av dette symbolet, har ordet lengde tre — det er satt sammen av symbolene «qw», «c» og «qw». Alfabeter av denne typen møter vi ikke særlig ofte, men det finnes situasjoner der vi trenger symboler som består av flere symboler.

Formelt språk

Et (formelt) språk over alfabetet Σ er en vilkårlig delmengde av Σ^∗. For et språk L over alfabetet Σ gjelder altså L ⊆ Σ^∗. Eksempler på språk:

• I forrige del definerte vi alfabetet av sifre Σ= {0, 1, …, 9}. Kleene-stjernen er alle ordene som bare består av sifre. Hvis vi legger til regelen at ordet ikke kan begynne med null og ikke kan være tomt, får vi mengden av naturlige tall ℕ. Det gjelder ℕ ⊆ Σ^∗, så ℕ er et språk over alfabetet Σ.

• Til den forrige mengden av sifre kan vi legge til tegnet minus «-», slik at Σ= {0, 1, …, 9, −}. Kleene-stjernen er alle ord som består av sifre eller minustegn. Det betyr imidlertid at Kleene-stjernen også inneholder ord som «12-84-», «1-5-8» eller «-». Språket av hele tall ℤ lager vi ved å legge til tre regler:

  • Minustegnet forekommer ikke i ordet i det hele tatt, eller det står først i ordet.
  • Det første sifferet i ordet kan ikke være null, bortsett fra i ordet «0».
  • Hvert ord må inneholde minst ett siffer.

  Denne mengden beskriver mengden av hele tall, og den er en delmengde av mengden Σ^∗ — den er altså et språk over alfabetet Σ.

• La Σ= {0, 1}. Kleene-stjernen er da alle ord som består av nuller og enere. Et språk L over dette alfabetet kan vi for eksempel definere som mengden av alle ord som har akkurat tre enere. Vi kan også være mer kreative og si at språket L er mengden av alle ord som er en gyldig docx-fil (det som kommer ut av Word).

• Vi blir værende ved det binære alfabetet Σ= {0, 1}. Hver streng av tegn (vanlige tegn som du har på tastaturet) kan gjøres om til binær form, altså til nuller og enere, og tilbake igjen, for eksempel ved hjelp av ASCII-tabellen (eller mer nøyaktig — ASCII-tabellen gjør om tegn til tall, og tall i titallsystemet kan skrives om til tall i totallsystemet). Dermed kan vi definere språket av alle ord som svarer til en gyldig e-postadresse, og det vil fortsatt være et språk over det binære alfabetet.

Sammenkobling av språk: vi kan også koble sammen språk. Definisjonen ligner på den for det kartesiske produktet av mengder. La oss ha to språk L₁ og L₂. Ved å koble dem sammen, L₁ ∘ L₂, får vi et nytt språk som vi definerer slik:

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

Altså tar vi alle ordene fra språket L₁ og kobler dem sammen med alle ordene fra språket L₂. Eksempel: La

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

Da gjelder:

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

Til nå har vi brukt vanlig språk til å beskrive språk, altså vi har med ord beskrevet hvordan språket skal se ut. Det er imidlertid veldig upraktisk, så man innfører en mer formell måte å definere et språk på. Den første av dem er grammatikk.