Skip to main content

Computation,Finite Automata,DFA,NFA,notations

      My Old Google site: Click("https://sites.google.com/site/cse09506mesce/home")

         1) Computation is the sequence of steps performed by the computer.

        2)Computation is the process of execution of an algorithm that involves take some inputs and apply some operation then will get some output. Output may be accepted or rejected based on the input string.



In My point of view eg:
       In neural network we having inputs,operation and outputs....Operation may be called as activation function.


          The word automata  comes from greek word automata that means "self acting".

self acting->Something is doing something by itself.

          we will see the term Automata.

 Automata-> is the study of abstract computing devices or machines.

Finite Automata-> is the mathematical model of a system with descrete inputs and ouputs.

FA divided into 2. 

DFA and NFA

DFA means Deterministic Finite Automata . 
From one state to another only one input symbol is using.

NFA means Non-Deterministic Finite Automata. 
There may be more than one transition from one state to another using same symbol.


DFA
5tuple(5 elements)
M=(Q,Sigma,Delta,q0,F)
Q->Finite number of states
Sigma->Finite number of symbols.

        Start State
     Final State
  Transitions
Example:


Comments

Post a Comment

Popular posts from this blog

DESIGN TM FOR {a^n b^n c^n | n>=1}

Concept:- General_idea: click_me L={a^n b^n c^n | n>=1} w={abc,aabbcc,aaabbbccc,....} a a a b b b c c c  X a a Y b b Z c c X X a Y Y b Z Z c Step_1: Replace a by X and go right side. TM tape can move any side. It has infinite memory in both side. And it can remember previous states details. Step_2: Replace b by Y and go right side of tape. Step_3: Replace c by Z and turn left till X .  Step_4: After seeing X(capital X) replace next a by X and do same loop. Step_5: X portions finished. Step_6: Move to Y states. Denote it for one move first and after that notate self loops. Goto final state Z in self loop. Finally stop turing machine. Success. Next step: How to add self loop states? Ok listen me... For that we are taking two steps X a a Y b b Z c c X X a Y Y b Z Z c  Just understand in between symbols. And make it as self loops. If any doubt please post comments..I can explain it. Small editing...This one...
Post a Comment
Read more

Design a TM(Turing Machine) , L={a^nb^n | n>=1}

Design View: By JFLAP Software Concept :  aaabbb Case1: XaaYbb Case2:XXaYYb Case3:XXXYYY Case 1: Read first 'a' and replace it by 'X' Then read first 'b' and replace it as 'Y' What i am doing is .....Meaning of a^n b^n is " Equal no: of a's must followed by equal no: of b's " In Case 1 : I read first 'a' and First 'b'. Before reading Second 'b'....Should read Second 'a' .... Then continue the steps.....Finally 'B' reads....Machine will stop... Transitions concept will continue ......
6 comments
Read more

Counter Machines

Counter machine has the same structure as the multi-stack machine  but in place of each stack is a counter. Counters hold any non-negative integer,but we can only distinguish between zero and nonzero counters. That's the move of the counter machine depends on its state,input symbol and which if any of the counters are zero. In one move,the counter machine can a)change state b)Add or subtract 1 from any of its counters,independently. However a counter is not allowed to become negative,so it cant subtract from a counter that is currently 0. Counter Machine may also be regarded as a restricted multi-stack machine. The restrictions are as follows, a)There are only two stack symbols,which we shall refer to as Z0(the bottom of stack marker) and X. b)Z0 is initially on each stack. c)We may replace Z0 only by a string of the form X^iz0 for some    i >=0. d)We may replace X only by X^i for some i >= 0. That's Z0 appears   only on the bottom of each stack and...
Post a Comment
Read more