23 Formelle språk og grammatikker Flashcards
konkatenering av to språk
Hvis L og M er språk, er konkateneringen (eng: concatenation) av L og M språket LM = {st | s ∈ L og t ∈ M}.
tillukning av et språk
Hvis L er et språk, er Kleene-tillukningen (eng: Kleene closure) - eller bare tillukningen - av L, språket L* = L^0 ∪ L^1 ∪ …, det vil si mengden av alle endelige strenger over L.
regulært språk
Mengden av regulære språk (eng: regular languages) 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.
regulære uttrykk
Mengden av regulære uttrykk (eng: regular expressions) 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
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).
deterministisk, endelig tilstandsmaskin
En deterministisk, endelig tilstandsmaskin (eng: deterministic finite automaton, DFA) består av følgende:
- En endelig mengde tilstander (eng: states)
- En endelig mengde inputsymboler (eng: inut symbols), også kalt et alfabet (eng: alphabet)
- En starttilstand (eng: start state), som er en av tilstandene
- En mengde aksepterende tilstander (eng: final/accepting states), som er en delmengde av tilstandene
- En overgangsfunksjon (eng: transition function), som er en funksjon som tar to argumenter - en tilstand og et inputsymbol - og som returnerer en tilstand
formell grammatikk
En formell grammatikk (eng: formal grammar), eller en grammatikk (eng: grammar), består av følgende:
- En endelig mengde terminalsymboler (eng: terminal symbols)
- En endelig mengde ikke-terminalsymboler (eng: nonterminal symbols).
- Et startsymbol (eng: start symbol), ett av ikke-terminalsymbolene
- En endelig mengde produksjonsregler (eng: production rules) 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.
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 (eng: derivation) av xn fra x1, og vi sier at xn kan utledes fra x1.
Språket (eng: language) som defineres av grammatikken er mengden av strenger som kan utledes fra startsymbolet S og som kun inneholder terminalsymboler.
regulær grammatikk
En regulær grammatikk (eng: regular grammar) 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.
kontekstfri grammatikk
En kontekstfri grammatikk (eng: context-free grammar) 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 (eng: context-free language).
