Euler's totient function

Its a very nice function on Natural numbers. A totient function on natural number n represented by φ(n) is defined as -
                  For prime p : -
                                 


Clearly φ(n) = # of mutual primes w.r.t n in the range of [ 1 ... n ].

Notation :- Z_n = [ 0 ... (n - 1) ]

Property : - 1. ∀ m,n ∈ Z ( Set of Natural Numbers ) s.t. gcd(m,n) = 1,
                             φ(m.n) = φ(m).φ(n)
                   2. ∀ m,n ∈ Z, φ(m.n) = φ(m).φ(n). gcd(m,n)/φ(gcd(m,n)) 
                   3.       
                   
                  4. For mutually prime a,n
                  5. 
                  6.  For ∀ a,n ∈ Z  and n > 1, 

If we inscribe  Möbius function and then some beautiful identity could be found.

For more see http://en.wikipedia.org/wiki/Euler's_totient_function

Language

In Automata-theory -

Alphabet :- Finite set of symbols.

String :- Sequence of symbols.

Language :- Set of strings.

Operations on Strings :- 
1. (+) - union

2. (.) - concatenation  

3. (*) - Kleene star 

Ex :-  A = "aa" B = "bb" 
1. A + B = {"aa","bb"} 
2. A.B = "aabb"

3. A^* = ε ∪A∪A²…

Notice that A^* the set of all finite strings over A.

Finite permutation of strings and above mentioned operations creates Regular Expression.

Regular Language :- 

Def 1 :- If -
             i. ∃ λ : Σ →  M is a  monoid homomorphism where M is a finite monoid.
             ii. S ⊆ M
then { ω∈ Σ^* | λ(ω) ∈ S} is regular.

Def 2 :- 
Let, L ⊆ Σ^*and there is an equivalence relation ~ s.t uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular ↔  Number of equivalence classes of ~ is finite.

A language L on alphabet Σ is Regular ↔ It is equivalent to a Regular Grammar
↔ It will have an Equivalent DFA ↔ It will have an Equivalent NFA.

Finite Automaton

We already described FA in the previous pages. There are 2 kinds of Finite Automaton, 1. DFA 2.NFA. Here introduced the concept of non-determinism and determinism.

Deterministic FA :- This is a FSM with a input string and a set of Accepting states (F). Formally a 5-tuple (Q,Σ,δ,q₀,F) represents the Structure. Here machine read the symbol , progress head one step right and take a deterministic jump [ A jump where from a current state one can go to a single next state ] from current state to new state with respect to the read symbol.

Non-Deterministic FA :- This is a non-deterministic FSM [ Normally FSM are deterministic but we can also make it non-deterministic by allowing multiple possible next state from current state w.r.t single read symbol . Control would choose totally  randomly  one of the next state from those possible next states, as it could only be in only one state at a time ].

Practically then for each symbol and each current state there will be multiple possible next state and so in a obvious consequence there could be multiple path of control flow and we don't know which path the control will go. But now we can say that the NFA will accept some string if ∃ at least one path ending in a accepting state.

So, formally NFA will also be a 5-tuple same as DFA, only difference is δ: Q × Σ  → 2^Q


With δ we sometime want to see the transition function for a string and we call it δ^'.
It is designed as -
1. ∀ (s,a) ∈ ( ( Σ^*- ε ), Σ ) → δ^'(s.a)  = δ^'(s).δ(a)
2. δ^'(ε) = φ

Finite State Machine

Def :- A Finite State Machine is a mathematical model of computation, as an abstract machine having a finite number of states ( forming set Q ) and transition between them. Also -

1. There is an finite sequence of symbols from a finite alphabet ( Σ = set of symbols ), 
2. One reading head is reading the string in left to right direction. 
3. There is a machine control which reside in only one state at a time. With the change of the time, a new symbol will be fetched from the string, reading head will go right and control moves from current state to next state according to transition function ( δ: Q×Σ → Q ).

Thus a FSM is typically a 3-touple (Q,Σ,δ) but if we inscribe a start state  q₀ , where machine control will initially reside, [ which makes things more convenient ]  then it become a 4-touple (Q,Σ,δ,q₀).

A FSM could be enhanced with adding a few more components. Suppose we add  a finite tape with input symbols and the machine will read one symbol at a time. Now the state transition occur according to the currently read symbol. 

 FSM and FA

Now, its a time to correct little correct ourselves. What I had told so far is obviously FSM but the definition of δ: Q×Σ → Q bound it in only a Deterministic zone. There is also a Non-deterministic FSM where  δ: Q×Σ → 2^Q. That is here the next state for a current state w.r.t a read symbol is not deterministic i.e. a not single state rather a state  randomly chosen from a set of states. 

While adding some more component we can construct some beautiful construct out of this. Let's color some state with a similar color / use flag for them and name them as Accepting State. With respect to a finite string if machine control halt in a Accepting state then we will say that the machine accepted that string. Now the set of acceptable string form a Language which would be accepted by that FSM. 

This above mention structure is called Finite Automaton.    

Lagrange Multiplier

Its a method of Solving optimization problem over Real field with respect to equality constraints.

Let, the problem P is :-

Find max f(x,y)

s.t.  g(x,y) = 0

Now,

1. We will make another function  φ(x,y,λ) = f(x,y) + λ . g(x,y).

2. We can say that  ∀p = (x₀, y₀) ∈ sp(P) [ sp(P) is Solution Space of problem P ] ∃λ₀ s.t. φ(x₀, y₀, λ₀) will be a stationary point.

i.e.  ∀(x₀, y₀) ∈ sp(P) ∃λ₀ ∈ ℜ s.t. φ(x₀, y₀, λ₀) will be a stationary point,
→  ∇_x,y,λ (φ) | _{(x0, y0, λ0)} = 0.

One Example :-

max ( x + y )
s.t. x² + y² = 1

φ(x, y, λ) = x + y + λ ( x² + y² - 1 )
∇_x,y,λ (φ) = ( 1 + λ x ; 1 + λ x ; x² + y² - 1) = 0 = ( 0 , 0 , 0 ) 
→ λ = √ 2 , ( x , y ) =  ( 1/√ 2 ,1/√ 2 )