$1$ Finite Automata $(20$ points$)$

Define the language that will be accepted by the following DFA. You can provide a verbal description of the language.

$2$ Substitution on a $CFL(20$ points$)$

Consider the CFL $L=\{a^n{b}^n|n0\}$ and the substitution $S(a)=\{0,00\}$ and $S(b)=\{1\}.$ Define the language $S(L).$

$3$ CYK Algorithm $(30$ points$)$

Use the CYK Algorithm to determine if the string aabba is in the language of the grammar below.

$SAB|BC|$

$ABA|a|$

$BCC|b|$

$CAB|a|$

$4$ PDAs$(30$ points$)$

Design a PDA which will accept the language consisting of strings over the alphabet $=\{a,b\}$ where number of $a\text{'}$s and $b\text{'}$s are not equal to each other. You can use maximum $5$ states in your PDA. Hint: Use an extra symbol!