FC1 Week 11 SGT

1

1. Give all computations and determine whether it is accepted.
   • $\square ◊\square ◊$ is accepted. $$\begin{array}{r}(s,\square ◊\square ◊),(s,◊\square ◊),(p,\square ◊),(s,◊),(p,ϵ)\end{array}$$

     title: Correct answer.

   • $\square ◊◊\square \square$ is rejected $$\begin{array}{r}(s,\square ◊◊\square \square ),(s,◊◊\square \square ),(r,◊\square \square ),(r,\square \square ),(r,\square ),(r,ϵ)\end{array}$$

     title: Correct answer.

   • $◊\square \square ◊\square ◊◊$ is rejected $$\begin{array}{r}(s,◊\square \square ◊\square ◊◊),(p,\square \square ◊\square ◊◊),(s,\square ◊\square ◊◊),(s,◊\square ◊◊),\\ (p,\square ◊◊),(s,◊◊),(r,◊),(r,ϵ)\end{array}$$

     title: Correct answer.

2. Any string without two consecutive $◊$s.

   title: Correct answer.

3. $◊\cup (◊\square \cup \square {)}^{\ast }$

   $$
   	(\square^* (\Diamond \square)^*)^* \cup (\square^*(\Diamond\square^*))^*\Diamond
   $$

2

1. Give all computations on input strings.

   • $bb$ is accepted $$\begin{array}{r}(s,bb),(s,b),\\ (s,bb),(s,b),(p,b),(r,ϵ)⇝\text{accepted}\\ (s,bb),(p,bb)\end{array}$$

     title: Correct answer.

   • $ab$ is accepted $$\begin{array}{r}(s,ab),(p,ab),(r,b)⇝\text{stuck}\\ (s,ab),(p,ab),(p,b),(r,ϵ)⇝\text{accepted}\end{array}$$

     title: Correct answer.

   • $aba$ is rejected $$\begin{array}{r}(s,aba),(p,aba),(p,ba),(r,a),(s,ϵ)⇝\text{rejected}\\ (s,aba),(p,aba),(r,ba)⇝\text{stuck}\end{array}$$

     title: Correct answer.

   • $ϵ$ is rejected $$\begin{array}{r}(s,ϵ)⇝\text{rejected}\\ (s,ϵ),(p,ϵ)⇝\text{rejected}\end{array}$$

     title: Correct answer.

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

3

Transform the DFA into an NFA using subset construction.

States: $\{\},\{s\},\{p\},\{r\},\{s,p\},\{p,r\},\{s,r\},\{s,p,r\}$ Favourable states: $\{r\},\{p,r\},\{s,r\},\{s,p,r\}$ Initial state: $\{s,p\}$

There is an $ϵ$-jump from $s$ to $p$ which means $r\to s,p$ by $a$.

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

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

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

4

Design an NFA that $L(A)$ consists of all the strings that start with $xx$ and end with $yy$ over $\{x,y\}$.

digraph {
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; e;
	node[shape=circle];
	init->a
	
	a->b [label=x]
	b->c [label=x]
	c->c [label=x]
	c->c [label=y]
	c->d [label=y]
	d->e [label=y]
	e->c [label=x]
}

	$x$	$y$	$ϵ$
$a$	$b$	$-$	$-$
$b$	$c$	$-$	$-$
$c$	$c$	$c,d$	$-$
$d$	$-$	$e$	$-$
$e$	$c$	$-$	$-$

5

Show that the language “all strings over the alphabet $\{0,1\}$ that contain $010$ as a substring and end with $01$” is regular.

Can be represented using regular expression:

$$(0\cup 1{)}^{\ast }(010(0\cup 1{)}^{\ast }\cup 10)01$$

6

Convert the following regular language to a finite automaton accepting it:

$$\text{Language\_of}((a\cup ab{)}^{\ast }(ba\cup (aa{)}^{\ast }b{)}^{\ast })$$

digraph {
	rankdir=LR
	init[shape=point]
	node[label="" shape=doublecircle] a, 0;
	node[shape=circle];
	init->a
	
	a->b [label=ε]
	b->c [label=a]
	c->a [label=ε]
	c->d [label=b]
	d->a [label=ε]
	
	a->0 [label=ε]
	
	z->x [label=a]
	x->y [label=a]
	y->x [label=a]
	y->w [label=b]
	
	1->2 [label=b]
	2->3 [label=a]
	
	0->z [label=ε]
	0->1 [label=ε]
	
	w->0 [label=ε]
	3->0 [label=ε]
}