Formelle sprog

Et formelt sprog er en slags generalisering af begrebet sprog, som vi kender fra hverdagen.

Grundbegreber

Et formelt sprog kan vi til at begynde med forestille os som et almindeligt sprog, for eksempel dansk. Hvad består et sådant sprog af? Det består af ord, som vi videre sætter sammen til sætninger. Sætningerne vil ikke interessere os, kun ordene. Hvad består ordene af? Af bogstaver i alfabetet. Vi begynder derfor med alfabetet.

Et alfabet er en vilkårlig ikke-tom mængde. Elementerne i alfabetet kalder vi symboler. Når det gælder dansk, er det det klassiske danske alfabet med både små og store bogstaver, inklusive æ, ø og å. Hvis vi ikke ville beskrive dansk, men for eksempel tal, ville vi have alle ti cifre i alfabetet. Alfabetet betegner vi ofte med symbolet Σ.

Ved et ord, eller en streng, forstår vi en endelig følge af symboler fra et alfabet Σ. Hvis vi for eksempel har alfabetet Σ= {a,b,c,d,e,…, z}, så er et ord for eksempel følgen »hej« eller »doberman«, men ikke »blåbær« (vi har ikke bogstaverne »å« og »æ«), »Hans« (vi har ikke bogstavet »H«) eller »god dag« (vi har ikke mellemrum). Ved ordets længde forstår vi antallet af symboler, som ordet består af.

Konkatenering af ord: hvis vi har to ord a = a₁a₂… a_n og b = b₁b₂… b_m, opstår der ved konkatenering af ordene ordet ab = a₁a₂… a_nb₁b₂… b_m. Eksempel: ved at konkatenere ordene »hej« og »doberman« opstår ordet »hejdoberman«. Konkatenering betegner vi enten med en bolle, dvs. a ∘ b, eller slet ikke, og så skriver vi bare ordene efter hinanden uden et særligt symbol for konkatenering.

Det tomme ord betegner vi ε, og det er ordet, der har længden nul. Hvis vi konkatenerer ordet a = a₁… a_n med det tomme ord ε, får vi ordet a tilbage. Dvs. a ∘ ε = a.

Afslutningen af alfabetet Σ er mængden af alle ord, som vi kan danne ud fra alfabetet Σ, inklusive det tomme ord. Afslutningen betegner vi Σ^∗. Hvis vi har det binære alfabet Σ= {0, 1}, gælder

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

Af og til bruger vi også den positive afslutning af et alfabet, som igen er alle de ord, vi kan sætte sammen af alfabetet, undtagen det tomme ord. Den positive afslutning betegner vi Σ⁺, og der gælder Σ⁺ = Σ^∗ ∖ {ε}.

Eksempler på alfabeter

• Vi vender tilbage til eksemplet med dansk. Hvert dansk ord finder vi i afslutningen af et alfabet, der indeholder små og store bogstaver og varianter med æ, ø og å (og måske også bindestreg »-«). Hvis vi til dette alfabet også tilføjer mellemrum og tegnsætning (komma, punktum, udråbstegn, spørgsmålstegn, …), får vi i afslutningen alle de sætninger, som vi kan danne på dansk. Selvfølgelig vil afslutningen også indeholde sætninger som »sadflsf kasdf kagrjewåæøker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf«, som dog stadig er mere meningsfulde end mange kommentarer på nettet.

• Hvis vores alfabet indeholder alle cifre Σ= {0, 1, …, 9}, vil afslutningen indeholde alle de naturlige tal — og nogle ekstra. Der vil nemlig også være tal, der begynder med nul, f.eks. 00054, eller nullet alene, og desuden vil der være det tomme ord, som naturligvis ikke er noget tal.

• Et alfabet skal være ikke-tomt, så det mindste alfabet har mindst ét symbol. For alfabetet Σ= {!} ville vi for eksempel få afslutningen Σ^∗ = {ε, !, !!, !!!, !!!!, …}, dvs. en mængde af ord, hvor der for hvert n ∈ ℕ₀ i afslutningen findes et ord med n udråbstegn, og intet andet ord i afslutningen findes.

• Lad Σ= {qw,c}. Det er et meget mærkeligt alfabet, fordi det indeholder ordet qw. Denne notation bruges normalt ikke, fordi den er forvirrende og underlig, men vi kan forestille os det sådan, at vi klistrer bogstaverne »q« og »w« sammen, så de udgør ét tegn. Så kan vi se ordet »qw« som symbolet »qw«. Hvis vi af dette symbol dannede ordet »qwcqw«, ville dette ord have længden tre — det ville være sammensat af symbolerne »qw«, »c« og »qw«. Vi støder ikke særlig ofte på den slags alfabeter, men der findes situationer, hvor vi har brug for sådanne symboler, der er sammensat af flere symboler.

Formelt sprog

Et (formelt) sprog over alfabetet Σ er en vilkårlig delmængde af Σ^∗. For et sprog L over alfabetet Σ gælder altså L ⊆ Σ^∗. Eksempler på sprog:

• I det foregående afsnit definerede vi et alfabet af cifre Σ= {0, 1, …, 9}. Afslutningen er alle de ord, der kun består af cifre. Hvis vi tilføjer reglen, at ordet ikke må begynde med nul, og at ordet ikke må være tomt, får vi mængden af naturlige tal ℕ. Der gælder ℕ ⊆ Σ^∗, så ℕ er et sprog over alfabetet Σ.

• Til den foregående mængde af cifre kan vi tilføje tegnet minus »-«, så Σ= {0, 1, …, 9, −}. Afslutningen er alle de ord, der består af cifre eller minustegn. Det betyder dog, at afslutningen også indeholder ord som »12-84-«, »1-5-8« eller »-«. Sproget for de hele tal ℤ danner vi ved at tilføje tre regler:

  • Tegnet minus forekommer slet ikke i ordet eller kun i begyndelsen af ordet.
  • Det første ciffer i ordet kan ikke være nul, undtagen i ordet »0«.
  • Hvert ord skal indeholde mindst ét ciffer.

  Denne mængde beskriver mængden af hele tal og er en delmængde af mængden Σ^∗ — det er altså et sprog over alfabetet Σ.

• Lad Σ= {0, 1}. Afslutningen er så alle de ord, der består af nuller og enere. Et sprog L over dette alfabet kan vi f.eks. definere som mængden af alle ord, der har præcis tre enere. Vi kan også være mere kreative og sige, at sproget L er mængden af alle ord, der udgør et gyldigt filformat for docx (det, der kommer ud af Word).

• Vi bliver ved det binære alfabet Σ= {0, 1}. Hver tekststreng (almindelige tegn, som du har på tastaturet) kan omdannes til binær form, dvs. til nuller og enere, og tilbage igen, for eksempel ved hjælp af ASCII-tabellen (eller mere præcist — ASCII-tabellen omdanner tegn til tal, og tal i titalssystemet kan omregnes til tal i det binære talsystem). Vi kan således definere et sprog af alle ord, der svarer til en gyldig e-mail, og det vil stadig være et sprog over det binære alfabet.

Konkatenering af sprog: vi kan også konkatenere sprog. Definitionen ligner den for det kartesiske produkt af mængder. Vi har to sprog L₁ og L₂. Ved deres konkatenering L₁ ∘ L₂ får vi et nyt sprog, som vi definerer sådan:

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

Dvs. vi tager alle ord fra sproget L₁ og konkatenerer dem med alle ord fra sproget L₂. Eksempel: Lad

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

Så gælder:

$$\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}$$

Hidtil har vi brugt almindeligt sprog til at beskrive sprog, vi har simpelthen med ord beskrevet, hvordan sproget skal se ud. Det er dog meget upraktisk, så man indfører en mere formel måde at definere et sprog på. Den første af dem er grammatikken.