2.2.1 Some more exercises
- Is every finite language regular?
- The "reverse" of a regular language is regular: if L is regular, so is {w-1 :
w ∊ L} where w-1 is w written backwards.
- You know that you cannot build a finite state machine that recognises
the matching bracket language. However you can build a machine that
accepts all and only those strings of matching brackets where the number
of outstanding opened left brackets never exceeds three.
Find a regular expression for the language accepted by this machine. (I
suggest that, in order not to drive yourself crazy, you write '0' instead of
the left bracket and '1' instead of the right bracket!!
Click for answer
How about the same for a machine that can cope with as many as five outstanding brackets?
Click for answer
- Find regular expressions for the regular languages in the CNF exercise in section 1.1.1.
Next: 2.3 Arden's rule and some stuff like that
Back: 2.2 Kleene's theorem