Tutorial Week 2 (Solutions)
Task 1. Here are the corresponding regular expressions.
• Binary numbers are given by (‘0’ | ‘1’)* and binary numbers divisible by 4 are 0 | (‘0’ | ‘1’)*00.
• Strings over the alphabet {w,x,y,z} where the first w precedes the first x and the first y: (‘x’ | ‘y’ | ‘z’)* | ( ‘z’* w (‘x’ | ‘y’ | ‘z’ | ‘w’ )* )
Task 2. None of these languages can be formalised by regular expressions. The problem is that regular expressions can’t count and don’t allow us to express stack-like behaviour.
Task 3. A plausible implementation is here. Many other implementations are possible.