The Gateway to Computer Science Excellence
0 votes
23 views
  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.
in Theory of Computation by Veteran (54.1k points) | 23 views

1 Answer

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
by Active (5k points)
edited by
0

@aditi19

$k=1 -> $

should be $11\left ( 0+1 \right )^{*}+1\left ( 0+1 \right )^{*}1$

0

@srestha

for which question you're saying?

0
1st one. Now  ok :)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,236 answers
194,256 comments
95,861 users