Posts

Showing posts with the label language

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

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

GRAMMAR IN THEORY OF COMPUTATION

-
Image
->Grammar is used as standard way to representing a language. ->It is used to check whether the given particular string is a part of the given language with some conditions, or not. -> It is  a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences .  -> Grammar is basically composed of two basic elements – Terminal Symbols – Terminal symbols are those which are the components of the sentences generated using a grammar and are represented using small case letter like a, b, c etc. Non-Terminal Symbols – Non-Terminal Symbols are those symbols which take part in the generation of the sentence but are not the component of the sentence. Non-Terminal Symbols are also called Auxiliary Symbols and Variables. These symbols are represented using a capital letter like A, B, C, etc. ->A grammar is defined as quadruple i.e.  EXAMPLE:-  S-->aSb/ ε -Here 'S' is the start symbol, 'a' & 'b' are terminals an...
2 comments
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