Tutorial Week 2
Task 1. Write down regular expressions for the following languages.
• Binary numbers, i.e. strings over the alphabet {0,1}, that are also multiples of four. Example 01 is not in the language, but 1000 and 1100 are.
• Strings over the alphabet {w,x,y,z} where the first w precedes the first x and the first y. I suggest to read this specification carefully, and ponder some examples strings like “wzxzyw”, “zzwzy”, “xw”, “zyw”. Which of those are in the language, which are not, and why?
Task 2. Can you write a regular expressions for the following languages?
• The language of all strings over {0, 1} having as many 0s as 1s? If not, why not?
• The language of all arithmetic expressions over {+, *, (, ), 0, 1, 2, …} having as strings all properly bracketed arithmetic expressions made from brackets, natural numbers and addition as well as multiplication?
• A programming language made up from simple assignments x = e, sequential composition P; Q which first executes P and then Q, while-loops of the form while x > 0 do P endwhile and conditionals of the form if0 e then P else Q endif. A program in this language might look like this: x = 1
• if x > 0 then
• while x < 10 do
• x = y
• endwhile
• else
• x = 9
• endif
•
• What is the relationship between the previous problems?
Task 3. Think about how you would represent programs of another language in Java so that you can efficiently do something with programs (e.g. print programs to the console). As an example, take language from the previous exercise, which has assignments x := e, sequential composition P; Q, loops whileGt0 e do P and conditiona if x > 0 then P else Q. For those of you who have seen the BNF-form already:
P ::= x := e | if0 e then P else P | whileGt0 e do P | P; P
e ::= e + e | e – e | e * e | (e) | e % e | x | 0 | 1 | 2 | …
Design a class hierarchy based on an suitable interface as base representing programs in this language. For the language above you could start with an interface Expr representing expressions, and an interface Prog for programs.