Ask Question
25 November, 09:13

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

+1
Answers (1)
  1. 25 November, 09:20
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers