• Main page

1.1.2 Some exercises

1. (a) Draw a machine that recognises the language {ε}. (This is easy but you might have to think hard about the notation!)
   
   (b) Draw a machine that recognises ∅, the empty language.

Click here for the answer


2. Explain what languages the following notations represent
   (a) {a²ⁿ : n ∊ ℕ};
   (b) {(ab)ⁿ : n ∊ ℕ};
   (c) {aⁿ b^m : n < m ∊ ℕ}
   You might like to design machines to recognise the first two.

Click here for the answer


3. For those of you who remember what CNF and DNF are. (If you don't yet know what CNF and DNF are, either find out or skip the question)
   (a) Propositional letters are p, p', p'', p'''. . . . This is a regular language.
   Exercise: Write a machine that recognises it.
   (Think: what is the alphabet?)
   
   (b) A literal is either a propositional letter, or a propositional letter preceded by a '¬'.
   The set of literals forms a regular language.
   Exercise: Write a machine that recognises it.
   (Think: what is the alphabet?)
   
   (c) A basic disjunction is a string like p ∨ ¬q ∨ r, namely a string of literals separated by '∨'. (For the sake of simplicity we overlook the fact that no literal may occur twice!)
   The set of basic disjunctions forms a regular language.
   Exercise: Write a machine that recognises it.
   (Think: what is the alphabet?)
   
   (d) A formula in CNF is a string of basic disjunctions separated by ∧, in the way that a basic disjunction is a set of literals separated by '∨'.
   The set of formulæ in CNF forms a regular language.
   Exercise: Write a machine that recognises it.
   (Think: what is the alphabet?)