Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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? – Rick Decker Oct 11 '12 at 1:19

You should probably edit your question with the work you've done.

First, your question seems ill-specified because you claim that $\delta^*$ is a function on $Q \times \Sigma^*$ but I really think you mean it's a function from $Q \times \Sigma^*$ to $Q$.

Next you need to consider what you might do induction on. You want to show that this function correctly produces some $q \in Q$ given any input $(q, w)$ with $q \in Q$ and $w \in \Sigma^*$. This may or may not be intuitive but since the definition of $\delta^*$ (in (a)) does not really make any assumptions about $q$ then it makes sense to induct on the length of $w$.

This leads to another issue which is how $\delta^*$ is defined on a single character or even the empty string (for your base case), but you can probably assume it's defined similarly to the definition of $\delta^*$ given in class. The induction step should follow naturally because the definition of $\delta^*$ is inductive...

share|cite|improve this answer
Sorry for type error. I take a picture of the question and the definition ( thanks! – Dyson Liu Oct 11 '12 at 10:25
You still need to update your original post with the work you've done. Honestly that question in the image is ill-specified in my head (maybe I'm crazy?). The intention seems relatively clear though, so you should still be able to work off it. Did you understand the basic approach I outlined in my answer? – roliu Oct 11 '12 at 22:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.