In the exercises you may need to include handwritten parts of the step-by-step commented solution. Highlight the final result at the end and clearly refer to the exercise number.

The solution and all the passages and comments must be clear and readable; you must complete the answer sheet within the set time limit.

Ensure you save your work as you go along.

The final version must be uploaded in PDF format.

All the pages (question file, answers file and any other file you want to submit) must be submitted as a single PDF file.

The filename must be in the following format: CandidateCode-ModuleCode- Coursework2.pdf

The deadline for submission is January 24, 2023, 5 PM GMT (UK time).

Each question is worth 20pt.

Exercise 1:

1)   Design a DFA that recognises all the strings over the alphabet {0, 1, F} (where F is  the final symbol), containing EXACTLY one substring with AT LEAST four consecutive 1s.

2)   Prove that the following language is not regular

L1  = {W =  0n 1n2}

Exercise 2:

1)   Prove that the following language is context free but not regular (note 1:  |w|

identifies the length of a string, note 2: the notation WR    identifies w reversed, so if W = ab, WR  = ba)

L2  = {WWR |W ∈ {a, b}, |W| even}

2)   Convert the grammar generated in Chomsky Normal Form, and build a parse tree for baab.

Exercise 3:

1)   Convert the following NFA into the equivalent DFA, showing the steps. After, draw  the graph and determine the language recognised (note: star * means final states):