Question

Show that if \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\) is a deterministic finite state automaton and f (s, x)=sfor the state s∈Sand the input string x∈I*, then \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{)}}\)=sfor every nonnegative integer n. (Here \({{\bf{x}}_{\bf{n}}}\) is the concatenation of ncopies of the string x, defined recursively in Exercise 37in Section 5.3.)

Short answer

Hence by the principle of induction, P(n) is true for all positive integers n and \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{) = s}}\) for every nonnegative integer n.

Step-by-step solution

Mention given details.

Given \({\bf{M = (S,I,f,}}{{\bf{s}}_{\bf{o}}}{\bf{,F)}}\) is a deterministic finite state automaton.

\({\bf{f }}\left( {{\bf{s, x}}} \right){\bf{ = s}}\)for the states \( \in {\bf{S}}\) and the input string\({\bf{x}} \in {\bf{I*}}\).

Proof by induction.

Let P(n) be \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{) = s}}\).

Put \({\bf{n = 0}}\) then:

\({\bf{f(s,}}{{\bf{x}}^{\bf{0}}}{\bf{) = f(s,\lambda ) = s}}\)

Since it remains at the start state when the input is the empty string\({\bf{\lambda }}\)

Thus p(0) is true.

Put \({\bf{n = k}}\) then \({\bf{f(s,}}{{\bf{x}}^{\bf{k}}}{\bf{) = s}}\)

Thus P(k) is true.

Now prove the result for\({\bf{P }}\left( {{\bf{k + 1}}} \right)\).

Since \({{\bf{x}}^{{\bf{k + 1}}}}{\bf{ = }}{{\bf{x}}^{\bf{k}}}{\bf{x}}\)

And \({\bf{f(s,xy) = f(f(s,}}{{\bf{x}}^{\bf{k}}}{\bf{),x)}}\)

Using,

\(\begin{array}{c}{\bf{f(s,}}{{\bf{x}}^{\bf{k}}}{\bf{) = s}}\\{\bf{f(s,x) = s}}\end{array}\)

Then \({\bf{f(s,xy) = f(f(s,}}{{\bf{x}}^{\bf{k}}}{\bf{),x) = f(s,x) = s}}\)

Thus \({\bf{P }}\left( {{\bf{k + 1}}} \right)\)is true.

Therefore, by the principle of induction, P(n) is true for all positive integers n and \({\bf{f(s,}}{{\bf{x}}^{\bf{n}}}{\bf{) = s}}\)for every nonnegative integer n.