23 Formelle språk og grammatikker Flashcards
23.1 Konkatenering av to språk
Hvis L og M er språk, er konkateneringen av L og M språket LM = {st | s ∈ L og t ∈ M}.
23.2 Tillukning av et språk
Hvis L er et språk, er Kleene-tillukningen - eller bare tillukningen - av L, språket L* = L0 ∪ L1 ∪ L<span>2</span> ∪ …, det vil si mengden av alle endelige strenger over L.
23.3 Regulært språk
Mengden av regulære språk over et alfabet A er den minste mengden slik at følgende holder:
- ∅ og {Λ} er regulære språk over A, og {a} er et regulært språk over A for alle a ∈ A.
- Hvis L og M er regulære språk, er L ∪ M, LM og L* også regulære språk.
23.4 Regulært uttrykk
Mengden av regulære uttrykk over et alfabet A er induktivt definert som den minste mengden slik at:
- ∅ og Λ er regulære uttrykk over A, og a er et regulært uttrykk over A for alle a ∈ A.
- Hvis R og S er regulære uttrykk, er (R), R|S, RS og R* også regulære uttrykk
23.5 Tolkning av regulære uttrykk
La A være et alfabet. Vi definerer en rekursiv funksjon L fra mengden av regulære ttrykk over A til mengden av regulære språk over A på følgende måte:
- L(∅) = ∅
- L(Λ) = {Λ}
- L(a) = {a}, for hver a ∈ A
- L(R | S) = L(R) ∪ L(S) (union)
- L(RS) = L(R)L(S) (konkatenering)
- L(R*) = L(R)* (tillukning)
I tillegg har parantesene ingen annen funksjon enn å gruppere: L( (R) ) = L(R). For ethvert regulært uttrykk E får vi på denne måten et regulært språk L(E).
23.6 Deterministisk, endelig tilstandsmaskin
En deterministisk, endelig tilstandsmaskin består av følgende:
- En endelig mengde tilstander.
- En endelig mengde inputsymboler, også kalt et alfabet.
- En starttilstand, som er en av tilstandene.
- En mengde aksepterende tilstander, som er en delmengde av tilstandene.
- En overgangsfunksjon, som er en funksjon som tar to argumenter - en tilstand og et inputsymbol - og som returnerer en tilstand.
23.7 Formell grammatikk
En formell grammatikk, eller en grammatikk, består av følgende:
- En endelig mengde terminalsymboler.
- En endelig mengde ikke-terminalsymboler.
- Et startsymbol, ett av ikke-terminalsymbolene
- En endelig mengde produksjonsregler på formen X → Y, hvor X og Y er strenger av terminal- og ikke-terminalsyboler og X ikke kan være den tomme strengen.
Vi antar at mengdene med terminal- og ikke-terminalsymboler er disjunkte og at det finnes minste én produksjonsregel med kun startsymbolet på venstresiden.
23.8 Utledninger
Anta at en grammatikk er gitt og at M er mengden av alle strenger over terminal- og ikke-terminalsymboler i grammatikken. La den binære relasjonen ⇒ være definert på M slik at AXB ⇒ AYB holder nøyaktig når X → Y er en produksjonsregel i grammatikken og A og B er strenger i M. En sekvens på formen x1 ⇒ x2 ⇒ … ⇒ xn kalles en utledning av xn fra x1, og vi sier at xn kan utledes fra x1. Språket som defineres av grammatikken er mengden av strenger som kan utledes fra startsymbolet S og som kun inneholder terminalsymboler.
23.9 Regulær grammatikk
En regulær grammatikk er en grammatikk hvor enhver produksjonsregel er på formen A → X, hvor A er et ikke-terminalsymbol og X består av maksimalt ett ikke-terminalsymbol som i så fall forekommer lengst til høyre.
23.10 Kontekstfri grammatikk
En kontekstfri grammatikk er en grammatikk hvor enhver produksjonsregel er på formen A → X, hvor A er et ikke-terminalsymbol og X en streng av terminal- og ikke-terminalsymboler. Et språk som defineres av en kontekstfri grammatikk kalles et kontekstfritt språk.
