Z is a language one the alphabet {A, B}. Z has all words with no repeated adjacent letters. For example, , AB, ABA, BABA are valid strings, whereas AA and ABBA are not.

a) Draw a DFS that recognises Z. Mark all states and labels. Justify it accepts all strings in Z and no others.

b) Devise a regular grammar in normal form that generates Z. Specify the start symbol, the non-terminals, and all the production rules. Justify it generates all strings in Z and no others.

c) Is Z Regular? Show by applying the definition of regular language.

d) Write down a regular expression that gives Z and justify your answer.