Practice Work

1

Given the following DFA:

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

Convert this DFA to an NFA.

• New states: $\{\{s\},\{p\},\{r\},\{s,p\},\{p,r\},\{s,r\},\{s,p,r\},\varnothing \}$
• Favourable states: $\{\{r\},\{p,r\},\{s,r\},\{s,p,r\}\}$
• Initial state: $\{s,p\}$

Transition table:

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

digraph {
	label="Full DFA"
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; r, pr, sr, spr;
	node[shape=circle] s, p, sp, 0;
	init->sp;
	
	s->r [label=a]
	s->r [label=b]
	p->r [label=a]
	p->pr [label=b]
	r->s [label=a]
	r->0 [label=b]
	sp->r [label=a]
	sp->pr [label=b]
	pr->sr [label=a]
	pr->pr [label=b]
	sr->sr [label=a]
	sr->r [label=b]
	spr->sr [label=a]
	spr->pr [label=b]
	0->0 [label=a]
	0->0 [label=b]
}

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

title: Incorrect answer.

2

1. Design a DFA or NFA that matches $101$ or $111$ as substrings.

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

title: Incorrect answer(?)

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

title: Correct answer.

2. Transition table of the DFA:

	0	1
p	q	t
q	s	r
r	r	r
s	s	p
t	q	r

title: Correct answer.