Tutorial Exercises

1

1. Deterministic
2. Find computations: $$\begin{array}{rlrl}ba& :(s,ba),(f,a),(f,ϵ)& & ⇝\text{accepted}\\ aa& :(s,aa),(q,a),(f,ϵ)& & ⇝\text{accepted}\\ ababab& :(s,ababab),(q,babab),(s,abab),(q,bab),(s,ab),(q,b),(s,ϵ)& & ⇝\text{rejected}\\ ababa& :(s,ababa),(q,baba),(s,aba),(q,ba),(s,a),(q,ϵ)& & ⇝\text{rejected}\\ ababb& :(s,ababb),(q,babb),(s,abb),(q,bb),(s,b),(f,ϵ)& & ⇝\text{accepted}\end{array}$$

title: Correct answers.

2

1. All strings over $\{0,1\}$ except empty string $ϵ$.

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

title: Correct answer.

2. All strings over $\{\alpha ,\beta \}$ that begin with $\alpha$ and end with $\beta$.

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

title: This should be a DFA not an NFA!

3

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

	$u$	$v$
$p$	$p$	$p$
$q$	$r$	$s$
$r$	$p$	$s$
$s$	$q$	$s$

title: Should contain 3 $u$s total not 3 $u$s in a row.

4

1. Nondeterministic

2. Describe using transition table.

   	$a$	$b$	$ϵ$
   $p$	$q$	$r$	$-$
   $q$	$-$	$p,r$	$-$
   $r$	$r$	$d$	$-$
   $s$	$h$	$-$	$p$
   $h$	$h,t$	$-$	$-$
   $t$	$-$	$t$	$d$
   $d$	$-$	$-$	$-$

title: Correct answers.

3. Find computations of: $$\begin{array}{rlrl}abb& :(s,abb),(p,abb),(q,bb),(r,b),(d,ϵ)& & ⇝\text{accepted}\\ abbbb& :(s,abbbb),(h,bbbb)\text{ (stuck)}& & \\ & :(s,abbbb),(p,abbbb),(q,bbbb),(p,bbb),(r,bb),(d,b)\text{ (stuck)}& & \\ & :(s,abbbb),(p,abbbb),(q,bbbb),(r,bbb),(d,bb)\text{ (stuck)}& & ⇝\text{rejected}\\ aabb& :(s,aabb),(p,aabb),(q,abb)\text{ (stuck)}& & \\ & :(s,aabb),(h,abb),(t,bb),(t,b),(t,ϵ),(d,ϵ)& & ⇝\text{accepted?}\end{array}$$

title: Correct answers.

5

NFA for matching bbab as a substring:

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

title: Correct answer.

6

Transform the following NFA into an equivalent DFA:

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

Favourable set: $\{\{q\},\{s,q\},\{q,p\},\{s,q,p\}\}$ Non-favourable set: $\{\{s\},\{p\},\{s,p\},\{\}\}$ Initial state: $\{s,p\}$

	$a$	$b$
$\{q\}$	$\{q,p\}$	$\varnothing$
$\{s,q\}$	$\{s,p,q\}$	$\{q\}$
$\{q,p\}$	$\{q,p\}$	$\{q\}$
$\{s,q,p\}$	$\{s,q,p\}$	$\{q\}$
$\{s\}$	$\{s,p\}$	$\{q\}$
$\{p\}$	$\varnothing$	$\{q\}$
$\{s,p\}$	$\{s,p\}$	$\{q\}$
$\varnothing$	$\varnothing$	$\varnothing$

digraph {
	label="Full DFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q, sq, qp, sqp;
	node[shape=circle] s, p, sp, 0;
	init->sp;
	
	q->qp [label=a]
	q->0 [label=b]
	sq->sqp [label=a]
	sq->q [label=b]
	qp->qp [label=a]
	qp->q [label=b]
	sqp->sqp [label=a]
	sqp->q [label=b]
	s->sp [label=a]
	s->q [label=b]
	p->0 [label=a]
	p->q [label=b]
	p->0 [label=a]
	p->q [label=b]
	sp->sp [label=a]
	sp->q [label=b]
	0->0 [label=a]
	0->0 [label=b]
}

digraph {
	label="Final DFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q, qp;
	node[shape=circle];
	init->sp;
	
	q [label="{q}"]
	sp [label="{s,p}"]
	qp [label="{q,p}"]
	0 [label="{}"]
	
	q->qp [label=a]
	q->0 [label=b]
	qp->qp [label=a]
	qp->q [label=b]
	sp->sp [label=a]
	sp->q [label=b]
	0->0 [label=a]
	0->0 [label=b]
}

title: Correct answer.