Question 1 a) Construct the state transition table for the nondeterministic finite state machine with the state transition diagram shown below

Question 1 a) Construct the state transition table for the nondeterministic finite state machine with the state transition diagram shown below.

Cs (5

\ Zz

b) Write the regular expression that can be accepted for the nondeterministic finite state machine above. (3 marks)

c) Find a deterministic finite state machine that recognizes the same language as the nondeterministic finite state machine in question | a). Show all the necessary steps in a state transition table.

Consider the finite state machine, M where the initial state is So, the input set is {0, 1} and the state transition diagram is shown below.

CONG

{> 0

| Loo

BY

a) Construct the state transition table of M. (4 marks)

b) Tabulate the word transition function fo110- (2 marks)

c) Find a partition of the state set corresponding to a machine congruence relation R with

as few classes as possible. (3 marks)

d) Construct the state transition table of the corresponding quotient machine. (2 marks)

Question 3 Construct the digraph of a Moore machine with five different states that has input elements a,

b, and accepts the input strings end with baba.

Question 4

Determine whether the binary operation on Z defined by x + y=x—3+y, Vx,yEZ

a) is closed, (2 marks)

b) is commutative, (3 marks)

c) is associative, (5 marks)

d) has an identity. (3 marks)

Justify your answer if the answer is ‘Yes’ and give a counterexample if the answer is ‘No’.

(Total: 13 marks]

Question 5

Determine whether the description of * is a valid definition of binary operation on the set.

Justify your answer.

a) On R*, where m +n = log,»n. (3 marks)

b) On Qt, where x + y = >: (3 marks)

(Total: 6 marks]

Question 6

Let G = (R*,x) be a group under the usual multiplication, x and Z* be the subset of R*. Determine whether Z* is a subgroup of R*. Show all the conditions to determine a subgroup and necessary steps to support your answer.