The Gateway to Computer Science Excellence
0 votes
94 views

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

  1. $\text{\{w| w begins with a 1 and ends with a 0\}}$
  2. $\text{\{w| w contains at least three 1s\}}$
  3. $\text{\{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)\}}$
  4. $\text{\{w| w has length at least 3 and its third symbol is a 0\}}$
  5. $\text{\{w| w starts with 0 and has odd length, or starts with 1 and has even length\}}$
  6. $\text{\{w| w doesn’t contain the substring 110\}}$
  7. $\text{\{w| the length of w is at most 5\}}$
  8. $\text{\{w| w is any string except 11 and 111\}}$
  9. $\text{\{w| every odd position of w is a 1\}}$
  10. $\text{\{w| w contains at least two 0's and at most one 1\}}$
  11. $\{\epsilon, 0\}$
  12. $\text{\{w| w contains an even number of 0's, or contains exactly two 1's\}}$
  13. $\text{The empty set}$
  14. $\text{All strings except the empty string}$ 
in Theory of Computation by Veteran (54.8k points) | 94 views

1 Answer

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)^+$
by Active (5.1k points)
edited by

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,647 questions
56,490 answers
195,433 comments
100,663 users