𝗧𝗘𝗖𝗛𝗗𝗥𝗘𝗔𝗠𝗘𝗥

  Simplification of Context Free Grammar Context Free Grammar  has recursive structure. The languages that are accepted with Context Free Grammar are called  Context Free Languages . Context Free Grammar has one condition for production rules, i.e.,  on the left-hand side of each rule, there must be only single variable, and on the right-hand side, there may be combination of variables and terminals including  ?. In Context Free Grammar, sometimes all the productions rules and symbols are not needed for the derivation to solve. Some productions rules are never used during derivation of any string. Elimination of these types of productions or symbols is called  Simplification of Context Free Grammar. We will use the various simple methods to simplify the given context free grammar without changing the resulting language. The following types of productions rules are never used during derivation of any string from context free grammar: Useless productions Null...

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...

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...

  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 + QP + RP...

  PUMPING LEMMA:- In the theory of  formal languages , the   pumping lemma   may refer to: -> Pumping lemma for regular languages , the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular. -> Pumping lemma for context-free languages , the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free. -> Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular. The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not mean that the language is regular. -> It states that if 'L' is an infinite ...