Regular Expressions & Translation of Regex to NFA

COMP218 Tutorials 2021-10-15

1. Give regular expressions for the following:

   1. The set of strings over alphabet $A=\{0,1\}$ that contains no two adjacent 1s:

      \[(1+\epsilon)(0^*01)^*0^*\]

   2. For the following state diagram:

       stateDiagram-v2
       direction LR
       [*] --> 1
       1 --> 1:a,b
       1 --> 2:b
       2 --> 3:a,b
       3 --> 4:a,b
       3 --> [*]
       4 --> [*]
      

      \[(a+b)^*b(a+b)(\epsilon +a+b)\]
2. Consider the following regular expressions which are given along with three words - for each word say whether it belongs to the language of the regular expression:
   1. $a^*b^*c^*d^*$
      • $abcd$ - Yes
      • $abbc$ - Yes
      • $aba$ - No
   2. $(ab)^*(abb)^*$
      • $ababab$ - Yes
      • $ababba$ - No
      • $ababbab$ - No

      For each pair of regular expressions below, say whether they represent the same language. If they correspond to different languages, give an example of a word that belongs to one language but not the other.

   3. $(a^*)\cup(b^*)$ and $\{a,b\}^*$ - No ($ab$)
   4. $\{a,ab,abc\}{d,cd}$ and $\{a,ab\}\{c,cd,d\}$ - No ($ac$)
   5. $(ab)^*\cup(aba)^*a$ and $a((ba)^*\cup(baa)^*)$ - No ($ab$)