Question

Show that if M = (S, I, f, s0,F)is a deterministic finitestate automaton and f (s, x) = s for the state s ∈ S and the input string x ∈ I ∗, then f (s, xn) = s for every nonnegative integer n. (Here xn is the concatenation of n copies of the string x, defined recursively in Exercise 37 in Section 5.3.)

Answer 1

we were able to show that f(s,x^n)=s holds for n>0

Explanation:

Given:

M=(S,I,f,so,F) a deterministic finite automaton

f(s,x)=s state s in S

proven f(s,x^n)=s for n>0

if n=0

f(s,x^0)=f(s,o)=s

if assume that f(s,x^n)=s prove that f(s,x^n+1)=s is true

the string of x^n+1 is:

x^n+1=(x^n)*x (eq. 1)

This can be written as:

f(s,x^n+1)=f(s,(x^n)*x) (eq. 2)

The states s of S we have:

f(s,xy)=f(f(s,x),y) (eq. 3)

equation 3 in equation 2:

f(s,(x^n)*x)=f(f(s,x^n),x) (eq. 4)

if f(s,x^n)=s is true, equation 4 will be equal to:

f(s,(x^n)*x)=f(f(s,x^n),x)=f(s,a)=s

we were able to show that f(s,x^n)=s holds for n>0