# proof using induction of automaton

How I can explain this. Consider the following automaton, $A$.

1. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s.

2. Show that there are words/strings with odd number(length) of $1$'s that does not belong to the language $L(A)$. Describe the language $L(A)$.

Here is what I did. For 1st question

q1 is the up-left circle , q2 the up-right, q3 down-left, q4 down-right.

and the transition table

     0  |  1
--------------
q1  q3    q4
q2  q2    q1
q3  q3    q4
q4  q2    q1


basic inductive step: I verify that is valid for word = 1 (odd number of 1's) From state q1 we go to q4 (final accept state)

induction hypothesis: I assume that is valid for n = 2 * k +1 (n odd number 1's)

inductive step: 2(k+1) +1 I prove that is valid for 2(k+1) +1=> 2(k+1) +3=> 2(k+1)

For second Suppose the word =1000 or 10 with odd length of 1's , the final state is not the acceptance one.

Can anyone tell me if this I wrote is correct?

In this case you might be able to state an invariant statement of the form: "For a word of the form $w1$ the unique path on $w1$ ends in state $q_0$ if $w$ contains an even number of $1$'s and in state $q_1$ otherwise".

The basis of the induction considers words $w$ with zero $1$'s, so look where $0^*1$ ends in. Then an inductive step, using the inductive hypothesis.

Start by assigning names to the states.

• Does it matter which state is q0,q1,q2 and q4? when you say 0* 1 what you mean? If you want to edit your answer to full answer – autstam Feb 9 '16 at 13:34
• q0 and q1 are just examples in my answer. The specific states needed to make a full solution are up to you. The expression 0*1 means any number of 0's followed by an 1. Full answer? This is all that is needed to start you in the right direction. – Hendrik Jan Feb 9 '16 at 15:53
• So , I wrote something different, can you tell me wether is correct or not? – autstam Feb 10 '16 at 20:38

You have three questions here; we are more comfortable with one question per post. Having said that, here are some hints.

For the first part, could you do the proof on the simpler language over $\{1\}$? In other words, ignore any 0's and see what you can do.

For the second part, what must a string in $L(A)$ end with?

Finally, welcome to the site!

• I'm not sure I follow your hint for the last part. For example, there are strings ending $10^k1$ in $L(A)$ for all $k\geq 0$ but there are also strings ending $10^k1$ that are not in $L(A)$ for all such $k$. (If you can't see a way to address this comment without giving away the answer, feel free to ignore it. Well, feel free to ignore it regardless. :-) ) – David Richerby Feb 9 '16 at 1:51
• I didn't understood the first one with induction.The effort I did you can see in the post. – autstam Feb 10 '16 at 20:39