Need help step by step

$+$ will be used to denote both alternatives $($as in $(1+2)$

$)$ and also to denote one or more applications

of Kleene star $($as in a

$+,$ meaning the language $\{$a

n

$|$n $>=1\}).$ You must take its application within

the context in which it is applied $($so you will need to use your brains!$).$

$$ Ranges such as all letters or all digits will be represented as $[$a $$ z$]$ meaning $($a $+$ b $+$ c $+$ d $+$ e $+$ f $+$

g $+$ h $+$ i $+$ j $+$ k $+$ l $+$ m $+$ n $+$ o $+$ p $+$ q $+$ r $+$ s $+$ t $+$ u $+$ v $+$ w $+$ x $+$ y $+$ z$).$ Hopefully the reason

for using ranges is obvious!

Historians have long debated the role and significance of the ceremony known as Stagscratch, which

appears to have been practiced for many centuries, including at the legendary school Pigwarts.

Ceremonies took place at irregular intervals, although never on the $30$th or $31$st of any month, and

involved a combination of up to three of four possible instruments, being bagpipes, drums, horns,

and lutes. Records of all Stagscratch ceremonies at Pigwarts since the year $500$ have been kept in a

handwritten archive, although there appear to have been no such ceremonies since the last recorded

on on $29$th December $1899.$ To save precious parchment and ink, the records of each ceremony

were kept as a string, using one character for each instrument $($b$,$ d$,$ h$,,$ and l respectively$)$ used, and

including the date, and the instruments used in that particular ceremony. Such strings were written

as follows.

CY$1$Y$2$M$1$M$2$D$1$D$2$SE

where

$$ C is the century indicator

$$ Y$1$Y$2$ are the last two digits of the year of the date

$$ M$1$M$2$ are two digits of the month of the date

$$ D$1$D$2$ are two digits of the day of the date

$$ S is the sequence of instruments used in the ceremony

$$ E is either the character a or the character z $($indicating what caused the ceremony to end$)1$

Note that C is either a single character in $\{5,6,7,8,9\}$ or string of length $2$ with the first character $1$

and the second in $[08],$ D$1$ is a single character in $\{0,1,2\},$ and M$1$ is a single character in $\{0,1\}.$

While no ceremony ever used more than three instruments, each instrument could be used any

number of times, and in any sequence, as long as at least one instrument was used. So the sequence

S can be any non$-$empty sequence of up to three instruments. For example, bdbdbdbh$,$ llllllllllldb

and hlhlhlhllll are all legal sequences of instruments, but lhdb and bbdhl are not $($because they both

contain four instruments$).$

Scribes also had the habit of omitting the century, year, month and day from an entry if they were

the same as the previous entry. For example the entry $5670122$bbbaddz indicates two ceremonies on

the $22$nd of January in the year $567,$ whereas the entry $18341007$dlbdlbdlba$08$bbbbbbbz indicates one

ceremony on $7$th October $1834$ and a second on $8$th October $1834.$

Ceremony records were written one after the other on the parchment as one enormous string. In order

to analyse the history of Stagscratch, it is necessary to write regular expressions to identify specific

matches of interest somewhere in this string. Scribes were attentive and diligent, but inevitably it

has been observed that there were occasionally errors made by scribes. This means that any regular

expressions for such purposes must be precise, and cannot assume that any given entry is error$-$free.

Give a regular expression for the following cases. In each case explain your answer.

i$.$ Any ceremony taking place before the year $1000$ in which neither drums nor bagpipes were

used.

ii$.$ Any ceremony in July or August after the year $1199$ which began with bagpipes followed

by drums.

iii. Any $$syntactically correct$$ record of a ceremony. This means the recorded entry must have

M$1$ being either $0$ or $1,$ D$1$ being $0,1$ or $2,$ include at most three instruments as above, a

correct $$end marker$$ and take into account the potential omission of the dates. Anything

not $$syntactically correct$$ must be an obvious error, such as the date $19994966$ or the

ceremony sequence bdlhnnnnq$.$

iv$.$ Any ceremony of the $7$th of some month in which exactly two instruments were used.

$($b$)$ Is it possible to give a regular expression for the following? Explain either why it is possible or

why it is not.

i$.$ Any two consecutive ceremonies which used exactly the same sequence of instruments.

ii$.$ The maximum number of times a given instrument is used in all of Pigwarts$$s history

iii. Any year in which no ceremony ever used a bagpipe.

iv$.$ Determining when, if ever, the lute has been used more than $1,000$ times in history.