Kapittel 23 – Formelle språk og grammatikker / Formelle grammatikker

Definisjon: Kontekstfri grammatikk

Hva syns du om denne videoen?
(Én stjerne er dårligst, tre stjerner er middels og fem stjerner er best.)
(Hvordan kan denne videoen bli bedre?)

Oppgave

Hvilke av disse grammatikkene er kontekstfrie, men ikke regulære?

Oppgave

La denne grammatikken være gitt, der $\str{0}$ og $\str{1}$ er terminalsymboler, mens $S$ og $A$ er ikke-terminalsymboler.

  • $S \rightarrow \str{0} \mid \str{1}A$
  • $A \rightarrow \tomstreng \mid \str{0}A \mid \str{1}A$

Hvilken type grammatikk er dette?