Question $4$: $(\frac{20}{100})$ : Please answer the following questions related to

NFAs, NFA to DFA conversions and REs.

a$)$ Convert to a DFA the following NFA and States are $Q=$

$\{p,q,r,s\}$ with State $s$ being a final state$)$:

b$)$ Design an NFA to recognize the following set of strings: abc,abd, and aacd

$(=\{a,b,c,d\}).$

c$)$ Consider the following $lon$ NFA $,$ States are $Q=\{p,q,r\},$

and the final states are $F=\{r\}).$

a$)$ Compute the $lon-$closure of each state.

b$)$ Give all the strings of length three or less accepted by the automa$-$

ton.

c$)$ Convert the automaton to a DFA.

d$)$ Write regular expressions $($REs$)$ for the following languages:

a$)$ The set of strings over alphabet $\{a,b,c\}$ containing at least one $a$

and at least one $b.$

b$)$ The set of strings over alphabet $\{0,1\}$ such that every pair of

adjacent $0\text{'}$s appears before any pair of adjacent l$\text{'}$s$.$

Justify all your answers show all your work.