Question

a. Writethe formal description of the following state machine (M 0. I irt So 0 0. 1 1.0

Answer 1

The machine is NFA,

Let us understand what language that can be accepted by the machine.

s3 and s5 are rejecting state because there is no way from these states to reach any final state.

First of all, the initial state is also a final state. So empty string would be accepted.

Now, If the string started with 0, it can go to s1 and s2, both. Assume if it goes to s2. At s2 there is self-transition for both inputs 0 and 1. And also s2 is a final state. So, we can safely say that all the string started with 0 can be accepted by the machine.

Now, if the string starts with 1, we need to go to state s1. We have a self-transition for 1 but if we get 0, we need to go to the rejecting state s3. So, if the string starts with 1, it should have all 1's to be accepted.

So, on summarising above things, three types of binary string accepted by the machine M:

1. empty string

2. strings started with 0

3. strings containing all 1's.

Formally,

Please upvote. Thanks.