$2$not Straightforward

$25$

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,

$]=[25$

$($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}.$

$2$

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}$

$($f$)$ Argue that

$L=\{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),n>0\}$

cannot be regular.