0
$\begingroup$

Let M = (Q,∑, q0,A, δ) be an FA. Below are other conceivable methods of defining the extended transition function δ∗. In each case, determine whether it is in fact a valid definition of a function on the set Q × ∑∗, and why. If it is, show using mathematical induction

a. For every q ∈ Q, δ ∗ (q,) = q; for every y ∈ ∗, σ ∈ , and q ∈ Q, δ ∗ (q, yσ ) = δ ∗ (δ ∗ (q, y), σ ).

b. For every q ∈ Q, δ ∗ (q,) = q; for every y ∈ ∗, σ ∈ , and q ∈ Q, δ ∗ (q, σy) = δ ∗ (δ(q, σ ), y).

c. For every q ∈ Q, δ ∗ (q,) = q; for every q ∈ Q and every σ ∈ , δ ∗ (q, σ ) = δ(q, σ); for every q ∈ Q, and every x and y in ∗, δ ∗ (q, xy) = δ ∗ (δ ∗ (q, x), y).

I stark at the first(a) , if i need to proof in induction what is the initial step

and n step to n+1 step? can you show me the proof?

thanks!

  • 0
    This is extremely hard to read. I started to format it for you but got hung up on (a). I guessed what you meant by $\delta^*(q,\ )=q$, but I was lost at the next part: $y\in *,\sigma\in$. At that point I simply gave up. Could you attempt to reformat it or at least explain what your notation means?2012-10-11

1 Answers 1