Automata Theory

[oops]

Hey,

I recently enrolled in an automata theory class, not realizing that the subject extensively used proofs. I am having a lot of trouble getting into the "proof" mindset and the notation and strategies used.

One problem that I'm having difficulty with is:

Suppose M = (Q,\sigma, q_0, A, \delta) is an FA, q is an element of Q and x and y are strings in \Sigma^* = {a,b}. Using structural induction on y, prove that:

\delta^*(q,xy) = \delta^*(\delta^*(q,x),y), where delta refers to the transition function between states.

This seems fairly obvious to me; you feed in characters of a string one at a time to an FA, so it will be at the same state no matter what. But I'm having trouble expressing it in a proof

I know that I can use induction to create the string xya and then prove \delta^*(q,xya) = \delta^*(\delta^*(q,x),ya). but I don't know where to go from there other than \delta^*(\delta^*(q,xy),a) or perhaps \delta^*(\delta^*(\delta^*(q,x),y),a)

Any suggestions on how I should complete the proof? Also, any advice on how to get better at proofs is welcomed.

[jareds]

Let y = a sequence of characters c1 c2 c3 ... cN (the empty string if N is 0).
Expressing y as such, what would you say that the base case and the inductive case of the induction are?

[Yakk]

You'll want to look at the formal definition of Delta star, because you want to formally prove things about it.

I could guess at a formal definition, but it might not be the right one. And as this is a technical point, how you prove it is going to be determined by the technical details of delta star.

Another thing that matters is the "maturity" level of the course. Are you expected to use some rigid definition of induction with a particular pattern? Or is the equivalent of strong induction, weak induction and the well ordering principle casually assumed?

I will say one thing you should watch out for -- the length 2 case could easily be a special case.

[oops]

I looked up the formal definition of \delta^* and I found something important:

\delta* : Q x \Sigma^* -> Q Where Q is a state of the finite autonama and sigma is the alphabet of the language L

For every q\, \epsilon\, Q, and every y,\, \epsilon\, \Sigma^* and every \sigma\, \epsilon\, \Sigma, \delta*(q,y\sigma) = \delta(\delta^*(q,y), \sigma)

Using this definition, I constructed this proof:

Hypothesis: x is in \Sigma^*, and y is a letter in \Sigma
Induction case: if the length of y is equal to 1, this property applies, since the definition of \delta^*, \delta^*(q,y\sigma) = \delta(\delta^*(q,y), \sigma),
Induction step: For all y of length n > 1, this is also valid in the extended transition function.
Proof:
\delta^*, \delta^*(q,xy) = \delta(\delta^*(q,x(y-1)), \sigma) where y-1 refers to y, with the last letter y_n removed from it.
\delta^*, \delta(\delta^*(q,x(y-1)), \sigma) = \delta(\delta(\delta^*(q,x(y-2)), y_{n-1}), y_n),
.
.
.
\delta(\delta(\delta^*(q,x)), y_0 ), y_1,),...),y_n)

From the definition of the transition function, this is equal to (\delta^*(q,xy))
Is this acceptable?

[Yakk]

Your proof contains errors in the 3rd line. The length of a single character in sigma is going to be 1. I suspect you are messing up x and y.

On line 5, the letter sigma comes form nowhere.

Your proof contains "...". "..." is typically not a valid proof step, but a sign of a gap in the proof.

What is your proof writing and reading experience?

[oops]

What is your proof writing and reading experience?

There was a geometry class in high school that I didn't really pay attention in, and I read the chapter of the textbook that covers proof strategies, but it assumed you were familiar with the material, so I don't really have any experience.

[Yakk]

Hypothesis: x is in \Sigma^*, and y is a letter in \Sigma

So x is a string, and y is a letter in your language.

Ok. Next, this isn't a Hypothesis. It defines two variables. It doesn't actually make a claim that anything is true. Hypothesis have to do this.

Traditionally in an inductive proof, you make a claim about something with a length parameter (or some integer parameter). Such as, for all n, and for all strings (or pairs of strings) of length n (or up to length n), something is true.

Induction case: if the length of y is equal to 1, this property applies, since the definition of \delta^*, \delta^*(q,y\sigma) = \delta(\delta^*(q,y), \sigma),

Here you are talking about the length of a single letter. It appears you are getting x and y mixed up. This is bad.

Second, I think you are trying to talk about what is traditionally called the "base case" of the induction not the "induction case".

Third, note that you missed n=0. That can be ok -- but then prove the n=0 case separately. (It is less ok in a "cargo cult" induction class, where following the form is more important than the content. "Cargo cult" induction is relatively common in lower level CS courses.)

Don't get me wrong -- following the pattern is great if you don't know what you are doing! But my problem is I don't know the pattern for your course, so I have to make up my own, which might be the wrong one.

Induction step: For all y of length n > 1, this is also valid in the extended transition function.
Proof:
\delta^*, \delta^*(q,xy) = \delta(\delta^*(q,x(y-1)), \sigma) where y-1 refers to y, with the last letter y_n removed from it.
\delta^*, \delta(\delta^*(q,x(y-1)), \sigma) = \delta(\delta(\delta^*(q,x(y-2)), y_{n-1}), y_n),
.
.
.
\delta(\delta(\delta^*(q,x)), y_0 ), y_1,),...),y_n)

I mentioned that the ... above is hand waving. Can you explain what is going on in it?

Have you seen an inductive proof before? Can you transcribe a simple one?

As an example, how about "all positive numbers can be written as a sum, possibly empty, possibly containing duplicates, of odd numbers". That is an example of something that can be proven by induction.

Hypothesis: Let P(n) be the statement that n can be written as the sum of odd numbers. I claim P(n) is true for every integer greater than or equal to zero.

Base Case: P(0). Sum{} = 0, and {} is a set of odd numbers (an empty set of odd numbers).

Inductive case: I will assume for all 0 <= x < k, P(x) is true. If k=0, the base case holds. If k>0, then let z = k-1.

We know that P(z) is true, as z >= 0. Let (a_i) be some collection of odd numbers such that sum a_i = z. Then sum (a_i) + 1 = z + 1 = k-1+1 = k.

So the collection a_i with 1 added satisfies our hypothesis.