Tutorial Exercises

1

• $a$
• $ab$
• $aab$

title: Wrong answer.
Correct answers: $ab, aba, abb, aab$

2

1. Does not belong in the regular language.
2. Belongs in the regular language.
3. Belongs in the regular language.

title: Correct answers.

3

1. $a^{\ast }(b\cup abb)b^{\ast }b$
   • $bb$
   • $abb$
   • $bbb$

   title: Correct answer.

2. $(a\cup ab)(a^{\ast }\cup ab{)}^{\ast }b$
   • $ab$
   • $aab$
   • $abb$

   title: Correct answer.

4

1. $a^{\ast }aab{b}^{\ast }$
   • $b$
   • $ba$
   • $bb$

   title: Wrong answer.
   Can be $\epsilon, a, b$

2. $(aa{)}^{\ast }(bba{)}^{\ast }(bb{)}^{\ast }$
   • $a$
   • $b$
   • $ba$

   title: Correct answer.

3. $a^{\ast }(bba{)}^{\ast }{b}^{\ast }$
   • $ba$
   • $baa$
   • $baaa$

   title: Wrong answer.
   Can be $ba, aba, bab$

5

Let $S=\{\alpha ,\beta \}$.

1. ${\beta }^{\ast }\alpha {\beta }^{\ast }$
2. $\alpha \alpha (\alpha \cup \beta {)}^{\ast }$
3. $\alpha \alpha (\alpha \cup \beta {)}^{\ast }\beta \beta$
4. $(\alpha \cup \beta {)}^{\ast }(\alpha \alpha \alpha \cup \beta \beta \beta )(\alpha \cup \beta {)}^{\ast }$

   title: Correct answers.

5. No answer.

   title: Wrong answer.
   Actual answer is $\beta^*(\alpha\beta^*\alpha\beta^*)^*$

6

Let $S=\{0,1\}$. Show that the language $L=\{w|w\text{ is a word over }S,\text{ and }0110\text{ is a suffix of }w\}$ is regular.

The language is regular because there is a regular expression representing it, e.g. $(0\cup 1{)}^{\ast }0110$

title: Checked solutions on how to answer this Q.

7

1. Convert $\text{Language\_of}((a\cup b{)}^{\ast }ab)$ to an NFA.

   digraph {
   	rankdir=LR
   	init[shape=point]
   	node[shape=doublecircle]; r;
   	node[shape=circle];
   	init->s
    
   	s->s [label=a]
   	s->s [label=b]
   	s->q [label=a]
   	q->r [label=b]
   }

2. Convert $\text{Language\_of}(((0\cup 11{)}^{\ast }1{)}^{\ast })$ to an NFA.

   digraph {
   	rankdir=LR
   	init[shape=point]
   	node[shape=doublecircle]; s;
   	node[shape=circle];
   	init->s
    
   	s->q [label=0]
   	s->r [label=1]
   	r->t [label=1]
   }

3. Convert $\text{Language\_of}(0(0\cup 11{)}^{\ast }(00\cup 11)11^{\ast })$ to an NFA.

   digraph {
   	sus
   }

title: Need to work on these.

8

1. $a{a}^{\ast }b{b}^{\ast }a{a}^{\ast }$

   title: Wrong answer.
   Correct answer: $\epsilon \cup aa^* bb^* a^*$

2. $(a\cup b{)}^{\ast }a(ba{)}^{\ast }a(ba{)}^{\ast }$

   title: Wrong answer.
   Correct answer: $(a \cup b)^*aa(ba)^*$

3. $(ab{)}^{\ast }(b\cup aa)(a\cup b{)}^{\ast }$

   title: Wrong answer.
   Correct answer: $b(a \cup b)^* \cup (a \cup b)^*(aa \cup bb)(a \cup b)^*$

4. $(a{a}^{\ast }a{b}^{\ast })\cup ((ab{)}^{\ast }(b\cup ab)a^{\ast }b)$

   title: Correct answer.