The Gateway to Computer Science Excellence

0 votes

Give regular expressions generating the languages of the alphabet is $\{0,1\}.$

- $\text{\{w| w begins with a 1 and ends with a 0\}}$
- $\text{\{w| w contains at least three 1s\}}$
- $\text{\{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)\}}$
- $\text{\{w| w has length at least 3 and its third symbol is a 0\}}$
- $\text{\{w| w starts with 0 and has odd length, or starts with 1 and has even length\}}$
- $\text{\{w| w doesn’t contain the substring 110\}}$
- $\text{\{w| the length of w is at most 5\}}$
- $\text{\{w| w is any string except 11 and 111\}}$
- $\text{\{w| every odd position of w is a 1\}}$
- $\text{\{w| w contains at least two 0's and at most one 1\}}$
- $\{\epsilon, 0\}$
- $\text{\{w| w contains an even number of 0's, or contains exactly two 1's\}}$
- $\text{The empty set}$
- $\text{All strings except the empty string}$

0 votes

a. 1(0+1)*0

b. 0*10*10*1(0+1)*

c. (0+1)*0101(0+1)*

d. (0+1)(0+1)0(0+1)*

e. 0((0+1)(0+1))* + 1(0+1)((0+1)(0+1))*

f. 0*+1*+(01)*+(10)*+(010)*

g. (0+1)(0+1)(0+1()(0+1)(0+1)

h. ε+0*+1+ 111$(0+1)^+$ + (0+10)*11$(0+01)^+$

i. (1(0+1))*(1+ε)

j. 0*(00+010+100+001)0*

k. ε+0

l. (1*01*01*)*+0*10*10*

m. Ф

n. $(0+1)^+$

b. 0*10*10*1(0+1)*

c. (0+1)*0101(0+1)*

d. (0+1)(0+1)0(0+1)*

e. 0((0+1)(0+1))* + 1(0+1)((0+1)(0+1))*

f. 0*+1*+(01)*+(10)*+(010)*

g. (0+1)(0+1)(0+1()(0+1)(0+1)

h. ε+0*+1+ 111$(0+1)^+$ + (0+10)*11$(0+01)^+$

i. (1(0+1))*(1+ε)

j. 0*(00+010+100+001)0*

k. ε+0

l. (1*01*01*)*+0*10*10*

m. Ф

n. $(0+1)^+$

52,345 questions

60,487 answers

201,827 comments

95,294 users