Kontekstfri grammatikk
Kontekstfri grammatikk er et sett med formelle regler som kan brukes til å beskrive og uttrykke både overordnet og detaljert struktur til språk og setninger. Kontekstfri grammatikk blir blant annet benyttet til å beskrive høynivå programmeringsspråk, og er nært relatert til kompilatorer og syntaks. Språket for en kontekstfri grammatikk er kalt et kontekstfritt språk.
- v
- d
- r
Automatteori: formelle språk og formelle grammatikker
Chomsky- hierarkiet | Grammatikker | Språk | Minimal automat |
---|---|---|---|
Type-0 | Uavgrensa | Rekursivt nummererbare | Turingmaskin |
Type-1 | Kontekstsensitiv | Kontekstsensitivt | Lineært bundet |
Type-2 | Kontekstfri | Kontekstfritt | Pushdown |
Type-3 | Regulær | Regulært | Endelig |
Hver kategori av språk eller grammatikker er en delmengde av kategorien rett over,
og hver automatisering i hver kategori har en ekvivalent automatisering i kategorien rett over.
og hver automatisering i hver kategori har en ekvivalent automatisering i kategorien rett over.
Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.