Consider the class of languages for $n0$ :

$L_n=\{w=w_1{w}_{2}cdots{w}_n|AAi,1in,w_{i}in\{0,1{\}}^{{?}^{?}}$#${?}_1(w_1{w}_{2}cdots{w}_i)>$#${?}_0(w_1{w}_{2}cdots{w}_i)\}$

That is$,L_n$ is the set of all $n-$bits strings where every prefix has more $1\text{'}$s than $0\text{'}$s$.$ For example,

$L_0=\{\}$

$L_1=\{1\}sub\{0,1\}$

$L_2=\{11\}sub\{00,01,10,11\}$

$L_3=\{110,111\}sub\{000,010,100,110,001,011,101,111\}$

$L_4=\{1101,1110,1111\}$

sub$\{0000,0010,0100,0110,0001,0011,0101,0111,1000,1010,1100,1110,1001,1011,1101,1111\}$

$L_5=\{11010,11011,11100,11101,11110,11111\}$

$L_6=\{110101,110110,110111,111001,111010,111011,111100,111101,111110,1111111\}$

cdots$=$cdots

$($a$)$ Show that $L_n$ is regular for $n0.$

$($b$)$ Let $win{L}_n,nk>0.$ Let us remove the last $k$ symbols $w_{n-k+1}{w}_{n-k+2}cdots{w}_n$ from $w$ to get $u.$

i$.$ Prove that $uin{L}_{n-k}.$

ii$.$ No string in an $L_n$ starts with a $0.$

iii. All strings in $L_n,n>1$ start with $11.$

$($c$)$ For $win{L}_n,n0,$ we define $d(w)=$#${?}_1(w)-$#${?}_0(w).$ Prove:

i$.$ If $d(w)=1,$ then $w1in{L}_{n+1}$

ii$.$ If $d(w)>1,$ then $w0in{L}_{n+1}^{{?}^{?}}w1in{L}_{n+1}$

iii. $d(w)-=n(mod2)$

$($d$)$ For $win{L}_n,n0,d(w)=$#${?}_1(w)-$#${?}_0(w),$ let $d_{i,j}=|\{w|win{L}_i^{{?}^{?}}d(w)=j\}|.i,j0.$ :

i$.$ Prove that $d_{i,j}=0,i+j-=1(mod2)$

ii$.$ Prove that the recurrence of $d_{i,j}$ is given by:

$d_{i,j}=d_{i-1,j-1}+d_{i-1,j+1},1i,j$

$=1,i=0,j=0$

$=0,i>0,j=0$

$=0,i0,j>i$

iii. Solve $d_{i,j}.$

$($e$)$ Let $f_n=|L_n|.$ Define $f_n$ recursively and solve.

Hint: $f_i={\displaystyle \underset{j}{\overset{?}{}}}{d}_{i,j}$