Question

Construct deterministic finite-state automata that recognize each of these sets from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet.

1. \(\emptyset \)
2. \(\left\{ {\bf{\lambda }} \right\}\)
3. \(\left\{ {\bf{a}} \right\}\), where \({\bf{a}} \in {\bf{I}}\)

Short answer

1. Therefore, the deterministic finite-state automata that recognize \(\emptyset \) set from\({\bf{I*}}\), where \({\bf{I}}\)an alphabet is shown below.

2.Hence, the deterministic finite-state automata that recognize \(\left\{ {\bf{\lambda }} \right\}\) set from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet shown below.

3. So, the deterministic finite-state automata that recognize\(\left\{ {\bf{a}} \right\}\), where \({\bf{a}} \in {\bf{I}}\) set from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet is shown below.

Step-by-step solution

General form

Finite-state automaton (Definition):

A finite-state automaton \({\bf{M = }}\left( {{\bf{S,I,f,}}{{\bf{s}}_{\bf{0}}}{\bf{,F}}} \right)\) consists of a finite set S of states, a finite input alphabet I, a transition function f that assigns the next state to every pair of states and input (so that \({\bf{f:S \times I}} \to {\bf{S}}\)), an initial or start state \({{\bf{s}}_0}\), and a subset F of S consisting of final (or accepting states).

Designing Finite-State Automata:

We often construct a finite-state automaton that recognizes a given set of strings by carefully adding states and transitions and determining which of these states should be final states. When appropriate we include states that can keep track of some of the properties of the input string, providing the finite-state automaton with limited memory.

Rules of regular expression represent a set:

\(\emptyset \)represents the empty set, that is, the set with no strings;

\({\bf{\lambda }}\)represents the set \(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

x represents the set\(\left\{ {\bf{x}} \right\}\) containing the string with one symbol x;

(AB)represents the concatenation of the sets represented by A and by B;

\(\left( {{\bf{A}} \cup {\bf{B}}} \right)\)represents the union of the sets represented by A and by B;

\({\bf{A*}}\) represents the Kleene closure of the sets represented by A.

Step 2: Construct the deterministic finite-state automata

Given that, the sets from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet.

Given set is\(\emptyset \)

Assume that, \({{\bf{s}}_0}\)is the starting point.

The start state \({{\bf{s}}_0}\) should be non-final because we don't want the machine to recognize any strings.

If the first input is an element, the string should still be rejected, and we can stay at.

The deterministic finite-state automaton that results will be unable to recognize any strings.

Note that \({\bf{I}}\) stands for all elements in the alphabet\({\bf{I}}\).

So, the diagram of the deterministic finite-state automaton is shown below.

Construct the deterministic finite-state automata

Given that, the sets from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet.

Given set is\(\left\{ {\bf{\lambda }} \right\}\).

Assume that, \({{\bf{s}}_0}\)is the starting point.

\({{\bf{s}}_0}\)should be the last state because the machine should accept the empty string \({\bf{\lambda }}\).

The string should not be accepted if it contains at least one element. As a result, if the first input is an element\({\bf{a}} \in {\bf{I}}\), we should go to state\({{\bf{s}}_1}\), which is a non-final state. We don't leave the state \({{\bf{s}}_1}\) once we've arrived (as the stings should not be recognized since they are not the empty string).

The deterministic finite-state automaton that results will recognize the empty string\({\bf{\lambda }}\).

Note that \({\bf{I}}\) stands for all elements in the alphabet\({\bf{I}}\).

So, the diagram of the deterministic finite-state automaton is shown below.

Construct the deterministic finite-state automata

Given that, the sets from\({\bf{I*}}\), where \({\bf{I}}\) is an alphabet.

Given set is\(\left\{ {\bf{a}} \right\}\), where\({\bf{a}} \in {\bf{I}}\).

Assume that, \({{\bf{s}}_0}\)is the starting point.

\({{\bf{s}}_0}\)should not be a final state because the machine should not accept the empty string\({\bf{\lambda }}\).

If the input is\({\bf{a}}\), we shift to state \({{\bf{s}}_1}\) as the final state (as the string should be accepted).

If the input is another element, we shift to state\({{\bf{s}}_2}\), which is a non-final state.

We will not exit the state once we arrive at \({{\bf{s}}_2}\) (thus \({{\bf{s}}_2}\) collecting all nonempty strings that should not be accepted).

If an input is received when we are at\({{\bf{s}}_1}\), the string should not be accepted, and we will be moved to the non-final state\({{\bf{s}}_2}\).

The deterministic finite-state automaton results will only recognize the string\({\bf{a}}\).

Note that \({\bf{I}}\) stands for all elements in the alphabet \({\bf{I}}\) and all elements in the alphabet \({\bf{I}}\) excluding \({\bf{a}}\) are represented by\({\bf{I}} - \left\{ {\bf{a}} \right\}\).

So, the diagram of the deterministic finite-state automaton is shown below.