SE 3M04 T1 2003
Possible answers for Sep 17 class work

To the question: Write down a BNF to describe all strings that do not contain aaa as a substring, one could use either

• a?( (ab) | (ac) | (ba) | (ca) | b | c )*a?
• ((a|aa)?(b|c))*(a|aa)?
• (a|aa)?((b|c)(a|aa)?)*

There are many other possible answers, but those above are the simplest.