حل تمرین نظریه محاسبات-ویرایش دوم/فصل اول/حل تمرین۱-۱۸

                                                                                                                        1-18 عبارت منظم زبان های زیر را بنویسید.

a.{w|w begins with a 1 and ends with a 0}

  1{0,1}*0

b.{w|w contains at least 3 1’s}

  {0,1}*1{0,1}*1{0,1}*1{0,1}*

c.{ w|w contains the substring 0101}

  {0,1}*0101{0,1}*

d.{w|w has length at least 3 and its third symbol is a 0}

  {0,1}{0,1}0{0,1}*

e.{w|w starts with 0 and has odd lengh or starts with 1 and has even lengh}

  0{00,01,10,11}*U1{00,01,10,11}*{0,1}

f.{w|w doesn’t contain the substring 110}

  {0}*U{0}*1U{0}*{10}*{0}*U{0}*11{1}*U{0}*{10}*1{1}*

g.{w|the length of w is at most 5}

  {ab}{a,b}{a,b}{a,b}{a,b}

h.{w|w is any string except 11 and 111} i.{w|w every odd position of w is a 1}

  {1,{0,1}}*

k.{}U{0}

  {}U{0}

l.{w|w contains an even number of 0’s or contains exactly two 1’s}

  {0,0}*U{0}*1{0}*1{0}*

m.the empty set

  Ø

n.all strings except the empty string

  {0,1}{0,1}*