2

http://web.cecs.pdx.edu/~black/CS311/proof_by_mutual_induction.pdf

I read this and I fail to see any difference. It's the same thing, prove for n = 0 and then prove for n = k+1.

user539484
  • 235
  • 1
    Looks the same; you're just proving the conjunction of a few different statements using induction, when maybe you only cared about one of them. – mjqxxxx Jan 22 '14 at 01:02
  • what do you mean by conjunction? do you mean you're proving the statements individually, or 1) because 2) and 3) needs 1 and 2) because 3) needs it. – user539484 Jan 22 '14 at 01:44

1 Answers1

2

Mutual induction is the most accurate way for proving L=L(A), 'L' being the language and "L(A)" being the language of a given automaton. The reason for this, is because you need to mutually prove that a certain string will transit through a certain state by a certain input and that transition depends on previous states. In other words, this method of proof clearly convinces that a certain language is accepted by the automaton by proving that a set of states will mutually lead to a final state by a given string.

O.A.
  • 392
  • So are you saying that in mutual induction you perform the inductive proof twice: first over the input and then over the set of states? So first you fix a state and then show that all inputs pass through the state, after which input is fixed and we consider the states instead? – sesodesa Mar 08 '20 at 12:23