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.)

Question

Mathematics

Cindy Delacruz

3 February, 18:31

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.)

+4

Answers (1)

Know the Answer?

Khalil · Answer 1

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

Step-by-step 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