Lecture No. 20

Dated: 02-01-2025

`Finite Automaton`¹ With Output

There are machines which take an input and generate a string² as output.
These machines are called machines with output and there are two types.

It consists of following

A finite set³ of states \(q_0, q_1, q_2, \ldots, q_n\) where \(q_0\) is the initial state.
An alphabet² of letters \(\Sigma = \{a, b, c, \ldots\}\) from which the input string² is formed.
An alphabet² of letters \(\Gamma = \{x, y, z, \ldots\}\) from which the output string² is formed.
A transition table showing for each state and each input letter, what state is entered next.
An output table showing what character is printed by each state as it is entered.

\[\text{States}: q_0, q_1, q_2, q_3\]

\[\Sigma = \{a, b\}\]

\[\Gamma = \{0, 1\}\]

Now running the string² \(abbabbba\) over the machine will output \(100010101\).

Input		a	b	b	a	b	b	b	a
State	\(q_0\)	\(q_1\)	\(q_1\)	\(q_1\)	\(q_3\)	\(q_2\)	\(q_3\)	\(q_2\)	\(q_0\)
Output	\(1\)	\(0\)	\(0\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)