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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,236 answers

194,256 comments

95,861 users