Classifying languages $(12$ points$)$: Consider the following list of languages over the alphabet

$\{a,b\}$

$\{a^n{b}^n|0n4\},\{b^n{a}^n|n3\},\{a^m{b}^n|0nm\}$

$\{a^m{b}^n|mn+2,n0\},\{b^m{a}^n|m3,n1\}$

$\{win\{a,b{\}}^{**}|w=w^R\},\{w{w}^R|win\{a,b{\}}^{**}\}$

$($a$)($Graded for completeness$)$ Pick one of the regular languages and design a regular expression

that describes it$.$ Briefly justify your regular expression by connecting the subexpressions

of it to the intended language and referencing relevant definitions.

$($b$)($Graded for completeness$)$ Pick another one of the regular languages and design a DFA that

recognizes it$.$ Draw the state diagram of your DFA. Briefly justify your design by explaining

the role each state plays in the machine, as well as a brief justification about how the strings

accepted and rejected by the machine connect to the specified language.

$($c$)($Graded for completeness$)$ Pick one of the nonregular languages and design a PDA that

recognizes it$.$ Draw the state diagram of your PDA. Briefly justify your design by explaining

the role each state plays in the machine, as well as a brief justification about how the strings

accepted and rejected by the machine connect to the specified language.

$($d$)($Graded for completeness$)$ Pick one of the nonregular languages and write a CFG that

generates it$.$ Briefly justify your design by by demonstrating how derivations in the grammar

relate to the intended language.