Practical application $2$: Context$-$free language recognizer.

$($a$)[3$ marks$]$ Design an algorithm that recognizes $($accepts$)$ strings of the following contextfree language: $L=\{\begin{array}{c}{0}^n{1}^n\end{array}$ : where $\{$:$n1\}.$ That is$,$ strings that contain a number of zeros followed by the same number of ones. Examples of strings in the language are: $01,0011,000111,$ etc. Strings that are not in the language are, for example, $10,00,111,1100,0101,$ and many more. The algorithm should take a string of $0\text{'}$s and $1\text{'}$s as input and output "Yes" if the string belongs to the language, and $"$No$"$ if the string doesn't belong to the language. The algorithm should use a stack. When it reads a $0$ from the string, it pushes $0$ onto the stack. When it reads a $1,$ it checks if the stack has a $0,$ in which case that $0$ is popped from the stack. When the stack is empty and the end of the string is reached, the string is recognized as correct $($Yes$).$ Otherwise, the string is not in the language $($No$).$

$($b$)[3$ marks$]$ Implement the algorithm of $($a$)$ in your favorite programming language and run it on different strings as follows: $01,000111,00000001111111,$ and $10,00,00111,0101,$ and others.

$($c$)[2$ marks$]$ Consider an input string of size $n$ : $($i$)$ what is the worst$-$case time that your algorithm takes to decide whether or not the string belongs to the language? $($ii$)$ Why? Give your answers in terms of the O$-$notation.

$($d$)[2$ bonus marks$]$ Run your algorithm on strings of lengths $n=2,4,8,16,32,$dots,$2^{20}.$ Compute the running time in nanoseconds and draw a table with the results. Draw a table or a plot of the results for different values of $n$ and compare the results obtained with the complexity you found in $($c$).$ Note: if all $($or most of$)$ the running times become $0,$ try running the program $1,000$ times and compute the average.