Deterministic Finite Accepters

Provide solutions to the following exercises. Solutions should be in the form of a hand$-$drawn transition

graph $($you may instead use a software tool like the Finite State Machine Designer$).$ Note: Text

descriptions and ASCII images will not be accepted.

Linz Section $2\mathrm{.}1$

For ${\displaystyle \underset{?}{\overset{?}{}}}=\{a$;$b\},$ construct DFAs that accept the sets consisting of

$($a$)$ all strings of odd length

$($b$)$ all strings of even length

$($c$)$ all strings of length greater than $5$

$($d$)$ all strings with an even number of a$\text{'}$s

$($e$)$ all strings with an even number of a$\text{'}$s and an odd number of b$\text{'}$s

For $=\{a$;$b\},$ construct DFAs that accept the sets consisting of

$($a$)$ all strings with exactly one a

$($b$)$ all strings with at least two a$\text{'}$s

$($c$)$ all strings with no more than two a$\text{'}$s

$($d$)$ all strings with at least one b and exactly two a$\text{'}$s

$($e$)$ all strings with exactly two a$\text{'}$s and more than three b$\text{'}$s

Give DFAs for the languages below:

$($a$)L=\{a{b}^{4}w{b}^2|win\{a,b{\}}^{**}\}$

$($b$)L=\{a{b}^n{a}^m|n3,m2\}$

$($c$)L=\{w_{1}abb{w}_2|w_{1}in\{a,b{\}}^{**},w_{2}in\{a,b{\}}^{**}\}$

$($d$)L=\{b{a}^n|n1,n4\}$

Show that the following languages are regular by constructing DFAs for each:

$($a$)L=\{a^n|n3\}$

$($b$)L=\{b^n{a}^{n}b|n2\}$

$($c$)L=\{a^n|n0$;$n3\}$

$($d$)L=\{\begin{array}{c}{a}^n|n\end{array}$ is either a multiple of three or a multiple of $5$