Theoretical Aspects of Computer Science

1
Theoretical Aspects of Computer Science

2
Contents
Theoretical Aspects of Computer Science.............................................................................................1
Question 1.............................................................................................................................................3
a.........................................................................................................................................................3
b.........................................................................................................................................................3
c.........................................................................................................................................................3
d.........................................................................................................................................................5
Question 2.............................................................................................................................................6
a.........................................................................................................................................................6
b.........................................................................................................................................................8
Question 3...........................................................................................................................................10
c.......................................................................................................................................................10
Question 4...........................................................................................................................................10
a.......................................................................................................................................................11
b.......................................................................................................................................................11
c.......................................................................................................................................................11
References...........................................................................................................................................12

3
Question 1
a
The given finite automaton is a non-deterministic finite automaton because the transition
from a state is at multiple next states for each input symbol. There are empty string
transitions as well which do not happens in DFA. Apart from this, there is more than one
final state which happens only in NFA (Hopcroft, 2011).
b
The non-deterministic finite automaton is defined by 5 tuples. Let M=(Q, ∑, ,q0,F) and w aẟ
string over ∑ where,
 Q is a finite set of states
 ∑ is a finite alphabet
 : Q * ∑ is the transition functionẟ
 q0 € Q is the start state
 F € Q is the set of accept states
c
Transition table
State(q) Input(a,b) Next State( (q,(a,b)))ẟ
0 a {1,4}

4
1 b {2}
1 a {ᴓ}
2 a {3}
2 b {ᴓ}
3 a {ᴓ}
3 b {1}
4 a {ᴓ}
4 b {5}
5 a {4}
5 b {ᴓ}
The strings which will be accepted are:
1. ∑={abab}
2. ∑={a}
3. ∑={aba}