Formelt språk

Eit formelt språk er i diskret matematikk ei mengd av strenger, som kan sjåast på som abstrakte ord. Formelle språk og typar av dei vert mykje brukte i informatikk, programmeringsteori og lingvistikk.

Definisjonar

Eit språk er definert i høve til eit alfabet. Eit alfabet Σ er ei endeleg, ikkje-tom mengd med vilkårlege symbol. Ein streng er då ein endeleg sekvens av symbol frå Σ. Til dømes, viss Σ = {a, b, c}, så er ein streng over Σ ein endeleg sekvens av bokstavane a, b og c, til dømes abbcb. Eit språk L er ei mengd (endeleg eller uendeleg) av strenger.

Det fulle språket over Σ, notert som Σ* (kleenestjerna av Σ), er det språket som inneheld alle strengene over Σ. Eitkvart språk L over Σ er dermed ei delmengd av Σ*. Enkelte språk, som Σ*, kan altså innehalde den tomme strengen ε, strengen som ikkje inneheld noko symbol.

Grammatikk

Ein formell grammatikk er ei mengd reglar som kan generere eit språk. Ein formell grammatikk er definert over to separate alfabet Σ (dei såkalla terminalsymbola) og N (ikkje-terminalsymbola), pluss eitt ekstra symbol S (startsymbolet). Grammatikken inneheld elles ei endeleg mengd P med avleiingsreglar på forma $\alpha \rightarrow \beta$ der α og β er strenger over $\Sigma \cup N$ og α inneheld minst eitt symbol i N. Regelen erstattar altså strengen α med strengen β, og grammatikken genererer eit språk L over Σ som inneheld alle strengene du kan gjere ved å

• starte med startsymbolet S,
• gjentekne gonger erstatte ein delstreng som er lik venstresida av ein avleiingsregel i P, med høgresida av den same regelen,
• heilt til du endar opp med ein streng der alle symbola er i Σ.

Høgresida av ein regel kan vere den tome strengen ε.

Det syner seg at dei språka som kan genererast av ein grammatikk er dei same språka som kan kjennast att av ei turingmaskin (dei såkalla rekursivt nummererbare språka). Chomskyhierarkiet inneheld fire grupper av språk som kan genererast av stadig meir restriktive reglar.