Posts

Showing posts with the label computation

ARDEN'S THEOREM FOR REGULAR EXPRESSIONS

-
Image
    Identities for Regular Expression:- Given R, P, L, Q as regular expressions, the following identities hold − ∅* = ε ε* = ε RR* = R*R R*R* = R* (R*)* = R* RR* = R*R (PQ)*P =P(QP)* (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)* R + ∅ = ∅ + R = R   (The identity for union) R ε = ε R = R   (The identity for concatenation) ∅ L = L ∅ = ∅   (The annihilator for concatenation) R + R = R   (Idempotent law) L (M + N) = LM + LN   (Left distributive law) (M + N) L = ML + NL   (Right distributive law) ε + RR* = ε + R*R = R* Arden's Theorem:- In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the properties of regular expressions. Statement  − Let  P  and  Q  be two regular expressions. If  P  does not contain null string, then  R = Q + RP  has a unique solution that is  R = QP* Proof  − R = Q + (Q + RP)P  [After putting the value R = Q + RP] = Q + ...
Post a Comment
Read more

EQUIVALENCE OF TWO FINITE AUTOMATAs

-
Image
An Automaton is a machine that has a finite number of states. Any Two Automaton is said to be equivalent if both accept exactly the same set of input strings.  Two Automaton are equivalent if they satisfy the following conditions :  1. The initial and final states of both the automatons must be same. 2. Every pair of states chosen is from a different automaton only. 3. While combining the states with the input alphabets, the pair results must be either both final states or intermediate states.(i.e both should lie either in the final state or in the non-final state). 4. If the resultant pair has different types of states, then it will be non-equivalent. (i.e. One lies in the final state and the other lies in the intermediate state). Method The method for comparing two FA’s is explained below − Let M and M1 be the two FA’s and Σ be a set of input strings. Step 1  − Construct a transition table that has pairwise entries (q, q 1 ) where q ∈ M and q 1  ∈ M 1  for eac...
Post a Comment
Read more

REGULAR EXPRESSIONS

-
       About R.E's. :- ->  The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language. ->The languages accepted by some regular expression are referred to as Regular languages. ->A regular expression can also be described as a sequence of pattern that defines a string. ->Regular expressions are used to match character combinations in strings. String searching algorithm used this pattern to find the operations on a string. What are Regular Languages?   – An alphabet Σ = {a, b, c} is a finite set of letters, – The set of all strings (aka, words) Σ∗ over an alphabet Σ can be recursively defined as:-  :Base case: ε ∈ Σ ∗ (empty string),  :Induction: If w ∈ Σ ∗ then wa ∈ Σ ∗ for all a ∈ Σ.  – A language L over some alphabet Σ is a set of strings, i.e. L ⊆ Σ ∗ . Some examples: – Leven = {w ∈ Σ ∗ : w is of even length} – La∗b∗ =...
Post a Comment
Read more

DETERMINISTIC FINITE AUTOMATA (D.F.A)

-
Image
About D.F.A :- ->In the  theory of computation , a branch of  theoretical computer science , a  deterministic finite automaton  ( DFA )—also known as  deterministic finite acceptor  ( DFA ),  deterministic finite-state machine  ( DFSM ), or  deterministic finite-state automaton  ( DFSA )—is a  finite-state machine  that accepts or rejects a given  string  of symbols, by running through a state sequence uniquely determined by the string.   Deterministic  refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines,  Warren McCulloch  and  Walter Pitts  were among the first researchers to introduce a concept similar to finite automata in 1943. ->It is defined as a five tuple consisting with- {Q,  Σ,  δ ,  q 0 ,  F } - a finite set of states 'Q' - a finite set of input symbols called alphabet  Σ - a transi...
Post a Comment
Read more

TYPES OF GRAMMAR IN T.O.C.

-
Image
  According to Noam Chomsky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. Let's see them one by one. Grammar Type Grammar Accepted Language Accepted Automaton Type 0 Unrestricted grammar Recursively enumerable language Turing Machine Type 1 Context-sensitive grammar Context-sensitive language Linear-bounded automaton Type 2 Context-free grammar Context-free language Pushdown automaton Type 3 Regular grammar Regular language Finite state automaton Take a look at the following illustration. It shows the scope of each type of grammar − Type 0 grammar:- Also known as unrestricted grammar generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars. T hey generate the languages that are recognized by a Turing machine.  A  Turning Machine  can simulate an  Unrestricted Grammar  and an  Unrestricted Grammar  can simulate  Turning Machine ...
Post a Comment
Read more

THEORY OF COMPUTATION

-
Image
  THEORY  OF  COMPUTATION(T.O.C.):- Theory of computation is a branch of computer science which deals with how a problem can be solved in an efficient way using what algorithms or model of computations. Here we solve the problems with different computational models, from which we get different states. This is a branch which give us an info about how computations are occurs in computer system or deals with theoretical model behind every computations. -For understanding completely about theory of computation, we have to deal with three main pillars of it i.e. L A G Language:- -It is a collection of all possible length of string of finite or infinite length. For example:-  aab, aabb, aaaabbbb, ahhbbb etc.  -The small unit of a language is known as 'symbol' or a language is a collection of more than one symbols. For example:-  {a, b, c, ........ 1, 2, 3, ..... etc.} -Finite set of symbols is known as 'alphabet' which is denoted by Sigma (Σ). For examp...
Post a Comment
Read more