Språket som defineres av grammatikken er mengden av strenger som kan utledes fra startsymbolet $S$ og som kun inneholder terminalsymboler.
Strengene $\str{aaabbb}$, $\str{aabb}$, $\str{aa}$ og $\str{aaaaa}$ er slike strenger:
Definisjon: Utledninger
Test deg selv
Gitt en grammatikk med terminalsymboler $\str{a}$ og $\str{b}$, ikke-terminalsymboler $S$, $A$ og $B$, startsymbol $S$ og produksjonsregler
- $S \rightarrow \str{aa}A$
- $A \rightarrow \str{a}A \mid B$
- $B \rightarrow \str{b}B \mid \tomstreng$
Hvilke av disse strengene er med i språket som defineres av denne grammatikken?
$S \Rightarrow \str{aa}A \Rightarrow \str{aaa}A \Rightarrow \str{aaa}B \Rightarrow \str{aaa}\str{b}B \Rightarrow \str{aaa}\str{bb}B \Rightarrow \str{aaa}\str{bbb}B \Rightarrow \str{aaabbb}$
$S \Rightarrow \str{aa}A \Rightarrow \str{aa}B \Rightarrow \str{aa}\str{b}B \Rightarrow \str{aa}\str{bb}B \Rightarrow \str{aabb}$
$S \Rightarrow \str{aa}A \Rightarrow \str{aa}B \Rightarrow \str{aa}$
$S \Rightarrow \str{aa}A \Rightarrow \str{aaa}A \Rightarrow \str{aaaa}A \Rightarrow \str{aaaaa}A \Rightarrow \str{aaaaa}B \Rightarrow \str{aaaaa}$