Peergrade assignment 6
(Resubmission)

1. Consider the finite-state automaton A with input alphabet {a, b} given
   by the following transition diagram:
   s0 s1 s2 s3
   b
   a
   b
   a
   b
   a
   a, b
   (a) Is the empty string accepted by this automaton?
   (b) Find three strings that are not accepted by this automaton.
   (c) Find three strings that are accepted by this automaton.
   (d) What is the language recognised by A? Describe the language
   using either set-builder notation or a regular expression.
2. For each of the following languages, construct a corresponding finitestate automaton with input alphabet {a, b} that recognises the language.
   (a) L = {w ∈ {a, b}
   ∗
   | |w|a ≤ 2}, i.e. the set of all strings with at
   most 2 occurrences of a.
   (b) L = {awb | w ∈ {a, b}
   ∗
   }.
3. There are three specifications for a graph listed below. For each of
   these specifications give either an example of a graph that satisfies
   the specification, or a formal argument why no such graph exists.
   (a) A graph with 4 vertices 7 edges and an Euler circuit.
   (b) A full binary tree with 8 vertices and total degree 14.
   (c) A simple connected graph with a circuit.