The Gateway to Computer Science Excellence

0 votes

- Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language.
- Let $C=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.

0 votes

a. B can be written as $1^k$(0+1)*

k=1 -> 1(0+1)*1(0+1)* y=(0+1)*1(0+1)*

k=2 -> 11(0+1)*1(0+1)*1(0+1)* y=(0+1)*1(0+1)*1(0+1)*

k=3 -> 111(0+1)*1(0+1)*1(0+1)*1(0+1)* y=(0+1)*1(0+1)*1(0+1)*1(0+1)*

B =1(0+1)*1(0+1)* $\bigcup$ 11(0+1)*1(0+1)*1(0+1)* $\bigcup$ 111(0+1)*1(0+1)*1(0+1)*1(0+1)* ..........

=(ε+11(0+1)*+111(0+1)*1(0+1)*+........)(1(0+1)*1(0+1)*)

$=(ε+11\sum^*)(1\sum^*1\sum^*)$

______________________________________________________________________

b.

k=1 -> 1(0*+0*10*) y=0*+0*10*

k=2 -> 11(0*+0*10*+0*10*10*)

k=3 -> 111(0*+0*10*+0*10*10*+0*10*10*10*)

C=1(0*+0*10*) $\bigcup$ 11(0*+0*10*+0*10*10*) $\bigcup$ 111(0*+0*10*+0*10*10*+0*10*10*10*)........

clearly there is no pattern

C is not regular

k=1 -> 1(0+1)*1(0+1)* y=(0+1)*1(0+1)*

k=2 -> 11(0+1)*1(0+1)*1(0+1)* y=(0+1)*1(0+1)*1(0+1)*

k=3 -> 111(0+1)*1(0+1)*1(0+1)*1(0+1)* y=(0+1)*1(0+1)*1(0+1)*1(0+1)*

B =1(0+1)*1(0+1)* $\bigcup$ 11(0+1)*1(0+1)*1(0+1)* $\bigcup$ 111(0+1)*1(0+1)*1(0+1)*1(0+1)* ..........

=(ε+11(0+1)*+111(0+1)*1(0+1)*+........)(1(0+1)*1(0+1)*)

$=(ε+11\sum^*)(1\sum^*1\sum^*)$

______________________________________________________________________

b.

k=1 -> 1(0*+0*10*) y=0*+0*10*

k=2 -> 11(0*+0*10*+0*10*10*)

k=3 -> 111(0*+0*10*+0*10*10*+0*10*10*10*)

C=1(0*+0*10*) $\bigcup$ 11(0*+0*10*+0*10*10*) $\bigcup$ 111(0*+0*10*+0*10*10*+0*10*10*10*)........

clearly there is no pattern

C is not regular

52,345 questions

60,497 answers

201,858 comments

95,315 users