Acceptance of strings and Languages

The string and languages can be accepted by finite automata, when it reached to a finite state. There are two preferred notations for describing automata:
   Transition diagram;
A transition diagram or transition graph can be defined as collection of-

1.      Finite set of states Q

2.      Finite set of symbols∑.

3.      A non empty set S of Q. it is called start state.

4.      A set F subset of Q of final states

5.      A transition  function Q x A-> Q with as state and A as input from ∑^*.

The notations used in transition diagram are-

Example:

The FA can be represented a using transition graph. The machine initially is in start state q₀ then on receiving input 0 it changes to state q_1. From q_{1 \}receiving input 1the machine changes its state to q₄. The state q₄ is a final state or accept state. When we trace the input for transition diagram and reach to a final state at end of input string then it is said that the given input is accepted by transition diagram.

Transition Table:

This is a tabular representation of finite automata. For transition table the transition function is used.

Input state	0	1
q0	q1	q2
q1	-	q4
q2	q3	-
q3	q4	-
q4	-	-

The rows of the table correspond to states and columns of the table corresponding to inputs.

Finite Automata Model

The finite automata can be represented as :

The finite automata can be represented using

Input tape- It is a linear tape having some number of cells. Each input symbol is placed in each cell.

Finite control- the finite control decides the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right and at a time only one input symbol is read.

Definition of Finite Automata

A finite automata is a collection of 5-components or tuple(Q,∑, δ,q₀ ,F) where

Q is a finite set of states, which is non empty.

∑ is a input alphabet, indicates input set,

q₀ is an initial state and q₀ is in Q i.e. q₀є Q

F is a set of final states.

δ is a transition function or a mapping function. Using this function the next state can be determined.

     δ:Q x ∑ ->Q

Finite State Machine

The finite state system represents a mathematical model of a system with certain input. The model finally gives certain output. The input when is given to the machine it is processed by various states, these states are called as intermediate states.

The very good example of finite state system is a control mechanism of elevator. This mechanism only remembers the current floor number pressed, it does not remember all the previously pressed numbers.

The finite state system is a very good deign tool for the programs such as text editors and lexical analyzer (which is used in compilers). The lexical analyzer is a program which scans your program character by character and recognizes those words as tokens.

operations on set

Operations on Set :

Various operations that can be carried out on set are

1. Union

2. Intersection

3. Difference

4. Complement

Union:            A U B is union operation – if A = {1, 2, 3} B = {1, 2, 4} then

A U B = {1, 2, 3, 4} i.e. combination of both the sets.

Intersection:   A ∩ B is intersection operation. If A = {1, 2, 3} B = {1, 2, 4} then

A ∩  B = {1, 2} i.e. common elements of the both the sets.

Difference:     A – B is the difference operation - if A = {1, 2, 3} B = {2, 3, 4} then

A – B = {1} i.e. elements which are there in set A but not in set B.

Complement:  is a complement operation – if   = U –A where U is a universal set.

For example:    U = {10, 20, 30, 40}

A = {10, 20}

Then  = U – A = {30, 40}.

Equal set

Equal set:

The two sets are to be equal (A = B) if A B and B A i.e., every element of set A is an element of B and every element of B is an element of A.

For example: A= {1, 2, 3} and B={1,2,3} then A = B.

|A| denotes the length of set A i.e. number of elements in set A.

For example: if A = {1, 2, 3, 4, 5} then |A| = 5.

Power set

Power Set: the power set is asset of all the subsets of its elements.

For example: A = {1, 2, 3}

Then the power set :Q = {ø, {1}, {2}, {3}, {1,2}, {1,3}, {3,2}, {2,3}, {1,2,3}}

The number of elements are always to 2ⁿ where n is number of elements in original set. As in set A there are 3 elements. Therefore in power set Q there are 2³ = 8 elements.

Null String

Null String: The null element is denoted by є or Λ character. Null element means no value character. But є does not mean ø.