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:

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

$L_3$ which contains exactly two as or exactly two bs$,$ although not necessarily adjacent.

$L_4$ which has all the bs appearing before any of the as$,$ or all the as appearing before any of the bs$.$

$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.

$L_2$ which has an odd number of bs and an even number of as$.$