encious

Automata are decision making machines, which decides whether a string belongs to a language or not. An automaton is called deterministic , when it shows a unique path for change of state on every input. Automata with definite number of states are called finite automata. A Deterministic finite automaton(DFA) has both qualities,ie. it is deterministic and has finite number of states A binary number is even if its LSB(Least Significant Bit) is zero (eg: 110 = 6 is even). If LSB is one, it is odd (eg: 111 = 7 is odd). So if we are constructing an DFA which accepts all odd binary numbers, our deterministic finite machine will have two states odd and even. set of of all states Q = {O, E} O - Odd E - Even Our machine requires inputs, the elemental binary numbers, i.e 0 or 1 These are called input alphabets Σ = {0, 1} When you feed this a DFA with a inputs from MSB(Most Significant Bit) to LSB of a binary, when the zero comes as input the stat...

The validation of a string for its membership in a language are handled by automata. An automaton acts as a acceptor of a string for a given language This is an example for an automaton which accepts all strings containing at least one 'a' . These circles are known as states. So X and Y are states. Circle with dual boundary (here Y ) is final state and one with unmarked arrow is initial state(here X ). Consider the string "baba", Initially we are at X , on seeing first alphabet 'b' the automaton loop back to X itself ( Edge with alphabet 'b' point to X itself). On seeing next alphabet 'a' , the state transition happens and reaches at new state Y . Once we reaches at state Y , both 'a' and 'b' loop back to the same state. So the string "baba" finally reaches as state Y Since the Y is the final state of this automaton, we can conclude that the sting "baba" belongs t...

Theory of computation or Automata theory mainly deals with abstract modeling of machines and computation. These models embody some of the important complex logical features we encounter, on dealing software as hardware. The following are the basic terminologies, which are frequently used in Theory of Computation Symbol The smallest building entity of Automata Theory( or Theory of Computation) is known as symbol. example: a, 2, i, B... Alphabet A set of symbols forms an alphabet. An alphabet is usually represented by Greek letter sigma( Σ ) example: Σ= { x, y} String A string is a sequence of symbols in a alphabet. example: 'xy' is a string derived from the alphabet Σ= { x, y} Language Collection of strings are called as a language. example: Let an alphabet Σ= { p, q, r} Then if a language L of set of a strings of length 2 over Σ can be represented as L = { pp, pq, pr, qp, qq, qr, rp, rq, rr } ...