Problem Specification

For each language L$1$ to L$5,$ described below, you need to do the following:

$$ Create a regular expression that defines the language. You will receive up to $7$ marks for each regular expression, depending on how accurately it defines the language. You must use the definition of regular expressions given in definition $7\mathrm{.}10$ using a different definition will lead to loss of marks.

$$ Construct a finite state automaton $($FSA$)$ that accepts the language, then pick a string that is in the language and show your FSA accepts it$,$ and pick a string that is not in the language and show your FSA rejects it$.$ You will receive up to $13$ marks for each FSA and tests, depending on their correctness.

Note that a total of $100$ marks are available for this assessment.

The alphabet A $=\{$a$,$ b$\}$ will be used throughout this coursework. The languages are:

$1.$ L$1$ which has exactly one b but any number of as$.$

$2.$ L$3$ which contains exactly two as or exactly two bs$,$ although not necessarily adjacent.

$3.$ L$4$ which has all the bs appearing before any of the as$,$ or all the as appearing before any of the bs$.$

$4.$ L$5$ where there can be any number of bs but the number of as must be even, although the as do not have to be adjacent.

$5.$ L$2$ which has an odd number of bs and an even number of as$.$