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

1

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

  • 0
    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?2012-10-11