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.

  • $\begingroup$ 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 $\endgroup$ – autstam Feb 9 '16 at 13:34
  • $\begingroup$ 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. $\endgroup$ – Hendrik Jan Feb 9 '16 at 15:53
  • $\begingroup$ So , I wrote something different, can you tell me wether is correct or not? $\endgroup$ – 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!

  • $\begingroup$ 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. :-) ) $\endgroup$ – David Richerby Feb 9 '16 at 1:51
  • $\begingroup$ I didn't understood the first one with induction.The effort I did you can see in the post. $\endgroup$ – autstam Feb 10 '16 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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