Question

.3.Show an NFA that accepts all binary strings with two 1’sin a row orthat contains three0’s in a row.

4.Convert the NFA from 3To a DFA

Answer 1

To design an NFA that accepts all binary strings with either two consecutive 1s or three consecutive 0s, start with a state that transitions to two patterns tracking each condition. To create a DFA from this NFA, use the subset construction method, which may result in a DFA with significantly more states than the NFA.

Step-by-step explanation:

Designing an NFA:

We must build states that monitor the occurrence of these patterns in order to design a non-deterministic finite automaton (NFA) that accepts all binary strings containing either two consecutive 1s or three consecutive 0s. Generally speaking, we don't need to monitor 0s for two consecutive 1s, and we don't need to worry about 1s for three consecutive 0s until we've seen at least one 0. An NFA that branches to two distinct tracking patterns, one for each condition, can be made.

Converting NFA to DFA:

The subset construction method needs to be used in order to transform the NFA into a deterministic finite automaton (DFA). To do this, new states representing subsets of states in the NFA must be created in the DFA. The procedure assigns distinct DFA states to each possible transition after methodically going over each possible combination of NFA states. Because every combination of NFA states must be represented, the transformation may require exponentially more states than the NFA.