Friday, December 24, 2010

Context Sensitive Grammar CSG

Context Sensitive Grammars are more general than Context Free Grammar ( CFG ) and less so than Unrestricted Grammars.

The corresponding model of computation called Linear Bounded Automata ( LBA ).

Linear Bounded Automata lie between Pushdown Automata ( PDA )and Turing Machine ( TM ).


Significance of the phrase "Linear Bounded":-

In Linear Bounded Automata ( LBA ) tape head's motion is restricted to a portion of the tape bounded by
some Linear function of the input length.

Sunday, December 19, 2010

Algorithm to Minimize DFA

Algorithm To Minimize Deterministic Finite Automata (DFA)

Step - 1
Mark Final States and Non Final States as Distinguished.

Step - 2
Recursively iterating over all pairs of states.
For any transition of the form

δ(p,x) = r   δ(q,x) = s 

and for some x є Σ, if r and s are distinguishable, mark p and q as distinguish.

Step - 3
If on any iteration over all possible state pairs one fails to find a new pair of
states that are distinguishable, terminate.

Step - 4
All states that are not distinguishable are equivalent.