416 views
0 votes
0 votes
  1. 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.
  2. 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.

1 Answer

0 votes
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
edited by

Related questions

0 votes
0 votes
0 answers
2
admin asked Apr 30, 2019
663 views
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\t...
0 votes
0 votes
0 answers
3