1) c) Ett sätt att tolka ("parsa") indata.
(Man kan också tolka a) som korrekt.)
2) Girig försöker matcha längsta möjliga sträng men motvillig nöjer sig med kortaste möjliga sträng:
text: aaabbbaaa
a.+a
girig matchning: aaabbbaaa
motvillig matchning: aaa
3) Omskrivningsregler (production rules eller rewriting rules)
4) a) 1111
b) 0110
5)
a) a*|a*b(aa*b)*a*
(Tidigare svar var felaktigt: (a*baa*)*|(a*ab)*)
b) ((a|b)(a|b)(a|b))*
c) (a|b)*|(a|c)*|(b|c)*
6)
<sms>::= <utrop><resten>|<resten>
<utrop>::= 'OMG'|'WTF'
<resten>::=<meddelande> <avslutning>
<meddelande>::= 'WHEREAREYOU'|'CALLME'|'YES'|'NO'|'ILOVEYOU'|'IHATEYOU'
<avslutning>::='LOL'|'SMILEY'|'FROWNEY'
7) (Obs att tidigare lösning var fel)
atom::=STRING | NUMBER | SYMBOL
sexpr::= atom
| '(' nyregel1
nyregel1::= ')'
| sexpr nyregel2
nyregel2::= '.' sexpr ')'
| sexprlist ')'
sexprlist::= (* empty *)
| sexpr sexprlist