Tutorial Exercises

1

1. $|w|=8$
2. $|w|=13$

title: Correct answers.

2

• $a$
• $b$
• $abbb$
• $bbba$
• $aaaaaaaaaaaaaa$
• $bbbbbbbbbbbbbb$

title: Correct answers.

3

1. $ϵ,01,0011,000111,00001111,0000011111$
2. $ϵ,00,01,10,11,0000,1111$
3. $ϵ,03,12,0123,\cancel{001233,011223}$

title: Partially correct.
3. $\epsilon, 12, 03, 0123, 0033, 1122$

4

1. In language: $aaa,bbb$ Not in language: $aab,baa$

   title: Correct answer.

2. For any $w$, we can find $|w|$. If we look at the set definition, it is defined that $ww=www$. Combining these words creates new words consisting of the two or more components.

   So, the left hand size becomes $|w|+|w|=2|w|$. The right hand size becomes $|w|+|w|+|w|=3|w|$.

   Hence we find that $2|w|=3|w|\to 2=3$ which is incorrect.

   Not in language: any word such as $aab$, $baa$.

   title: The only word in the language is $\epsilon$.

3. In language: $a$, $b$ There is no such $w$ that is not in the language, as regardless of what we set as $w$, $uvw=wvu$ holds provided that $u=w$ which is allowed and $v$ is any arbitrary word from $Z$.

   title: Correct answer.

5

$\varnothing$ may be a language over a set of words $S=\varnothing$ $\{ϵ\}$

title: Partially correct (incomplete)
Both $\emptyset$ and $\{ \epsilon \}$ can be sets of words over any alphabet $S$.

6

7

1. Description of automaton using transition table:

   	a	b
   s	q	t
   q	q	r
   t	t	t
   r	p	r
   p	p	t

   title: Correct answer.

2. Determine if accepted:

   • $aaabba$: ends at $p$ hence accepted $(s,aaabba),(q,aabba),(q,abba),(q,bba),(r,ba),(r,a),(p,ϵ)$
   • $aabaab$: ends at $t$ hence rejected $(s,aabaab),(q,abaab),(q,baab),(r,aab),(p,ab),(p,b),(t,ϵ)$
   • $aabbaab$: ends at $t$ hence rejected $(s,aabbaab),(q,abbaab),(q,bbaab),(r,baab),(r,aab),(p,ab),(p,b),(t,ϵ)$

   title: Correct answers.

3. Language is any amount of $a$ symbols followed by at any amount of $b$ symbols (potentially none) followed by any amount of $a$ symbols (potentially none).

   title: Partially correct.
   It consists of the empty string $\epsilon$ and all the strings of the form "a non-empty string of $a$s followed by $a$ (possibly empty) string of $b$s followed by a (possibly empty) string of $a$s".
    
   Formal definition: $\{ \epsilon \} \cup \{ a^nb^ma^k | n \in \mathbb N^+, m \in \mathbb N, k \in \mathbb N \}$

8

1. Describe $A$ with a state transition diagram

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

2. Find computations:

   • $aababa$: ends at $r$ hence accepted
   • $bbaababaa$: ends at $r$ hence accepted

   It is not true that $A$ accepts all strings of length $\ge 2$ ending with an $a$, take for example, the string $ba$, $bba$ or any arbitrary amount of $b$, this will result in leaving us at $q$ which is not a favourable state hence it will be rejected.

   title: Correct answers.

3. Find computations:

   • $aabaab$: ends at $q$ hence rejected $(s,aabaab),(q,abaab),(r,baab),(q,aab),(r,ab),(r,b),(q,ϵ)$
   • $bbaababb$: ends at $s$ hence rejected $(s,bbaababb),(q,baababb),(s,aababb),(q,ababb),(r,babb),(q,abb),(r,bb),(q,b),(s,ϵ)$

   title: Correct answers.

title: Questions (4) to (5) are not exam material.

4. $L(A)=\text{any string ending in two }a\text{ symbol or ending in }aba$

   title: Incorrect answer.
   Take any word of $a$ and $b$ which is folloewd by $aa$ then by any (possibly) zero number of repetitions of $ba$.
    
   $$
   	L(A) = \{ waa(ba)^n | w \text{ is any word of } a \text{ and } b \text{ symbols, and } n \in \mathbb N \}
   $$

5. no