Posts

Showing posts with the label context free 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

CONTEXT FREE GRAMMAR

-
Image
About C.F.G. :-   -> In   formal language   theory, a   context-free grammar   ( CFG ) is a   formal grammar   whose   production rules   are of the form {\displaystyle A\ \to \ \alpha } with  {\displaystyle A}  a  single   nonterminal  symbol, and  {\displaystyle \alpha }  a string of  terminals  and/or nonterminals ( {\displaystyle \alpha }  can be empty). A formal grammar is "context free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a  context-sensitive grammar . A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture, {\displaystyle...
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