Practice Work

1

Yes, provided that the initial state is a favourable state. For example, the DFA $A$ defined as:

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

If we try to input $\{ϵ\}$, we find that we start at $s$ and end at $s$, which is a favourable state hence the finite automaton accepts this input.

title: Correct answer.

2

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

1. Describe using a transition table.

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

title: Correct answer.

2. Find computations of input:

   • $(s,01101),(p,1101),(p,101),(p,01),(p,1),(p,ϵ)$

     Ends on $p$ hence rejected as $p$ is not a favourable state.

   • $(s,1010101),(q,010101),(q,10101),(r,0101),(r,101),(q,01),(q,1),(r,ϵ)$ Ends at $r$ hence accepted as $r$ is a favourable state.

   • $(s,1100111),(q,100111),(r,00111),(r,0111),(r,111),(q,11),(r,1),(q,ϵ)$ Ends at $q$ hence rejected as $q$ is not favourable state.

   title: Correct answer.

3. $L(A)=1\text{ followed by an odd number of }1\text{ symbols with any}$ $\text{amount of }0\text{ symbols between}$

title: Correct answer.