Posts

Showing posts with the label grammar

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