Prove by induction on the length of input strings \"w\" that L(M) = L = {w in {0

Question

Prove by induction on the length of input strings "w" that

L(M) = L = {w in {0,1}* | w has an even number of 1's}

(String w is 0 and/or 1, with even numbers of 1's)

(Actual Question End here)

Below is what i got so far

Base case. Length of w = 0;

Assume Inductive Hypothesis

S-even (n) - delta-hat (q0,x) = q0, if x has even number of 1's and length of x <= n.

S-odd (n) - delta-hat (q0,x) = q1, if x has odd number of 1's and length of x <= n.

Prove for S-even (n+1) and S-odd (n+1) assuming inductive hypothesis S-even (n) and S-odd (n).

Considered length of w = n+1, w = xa (String x = everything but last symbol in "w", a = last symbol in w).

Comment

Explanation / Answer

Yes The Given finite state in which Initial state is q0 and final state is q0 will have even number of 1 when we were on final state otherwise if we were on state q1 we will definetly going to have odd numbers of 1 in our string

Let us prove it by induction :-
Base Case:
   if Length of w = 0, we have even number of 1 in string w and we are on state q0.
Induction Hypothesis:
   if Length of w is odd (let say equal to n), our state will be q1 when w = xa and x has odd number of 1's and length of x <= n
  if Length of w is even (let say equal to n), our state will be q0 when w = xa and x has even number of 1's and length of x <= n
induction Step:
for now for length of w to be n+1, w = xa if we have odd number of 1 in x and n+1 digit is 1, then according to Induction hypothesis we were at state q1 and now n+1 digit is 1 so our state will be q0 and number of 1 in w is even.
   for now for length of w to be n+1, w = xa if we have odd number of 1 in x and n+1 digit is 0, then according to Induction hypothesis we were at state q1 and now n+1 digit is 0 so our state will be q1 and number of 1 in w is odd.
  for now for length of w to be n+1, w = xa if we have even number of 1 in x and n+1 digit is 1, then according to Induction hypothesis we were at state q0 and now n+1 digit is 1 so our state will be q1 and number of 1 in w is odd.
   for now for length of w to be n+1, w = xa if we have even number of 1 in x and n+1 digit is 0, then according to Induction hypothesis we were at state q0 and now n+1 digit is 0 so our state will be q0 and number of 1 in w is even.

so we will be on state q0 in final state if length of 1 in w is even otherwise on state q1.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.