Define Finite Automata. What is deductive and inductive proof?

Finite Automata: A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set ( or alphabet) C. The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

                A finite automaton consists of:

·         a finite set S of N states

·         a special start state

·         a set of final ( or accepting) states

·         a set of transitions T from one state to another labeled with chars C

There are two types of finite automata__

a) Deterministic finite automata.

b) Non- Deterministic finite automata.

  Deductive proof: A deductive proof consists of a sequence of statement whose truth leads us from some initial statement (hypothesis or given statements) to a conclusion statement. Each step of a deductive proof MUST follow from a given fact or previous statements ( or their combinations) by an accepted logical principle. The theorem that is proved when we go from a hypothesis H to a conclusion C is the statement “if H then C”. We say that C is deduced from H.

Induction proof: Induction means, proof something for all natural numbers by first providing that it is truth for 0, and that if it is true for n ( or sometimes, for all numbers up to n), then it is truth also for n+1.

Inductive Step:

Suppose a statements P(n) about a non integer n.

The principle of mathematical induction is that p(n) follows from

                                (a) P(0), and

                                (b) P(n-1) implies P9n) for n ≥ 1.

Condition (a) in the inductive proof is called the basis, and condition (b) is called the inductive step. The left hand side of (b), that is P(n-1) is called inductive hypothesis.