Regular vs Context Free Grammars

Question

I m studying for my computing languages test  and there s one idea I m having problems wrapping my head around     I understood that regular grammars are simpler and cannot contain ambiguity  but can t do a lot of tasks that are required for programming languages   I also understood that context-free grammars allow ambiguity  but allow for some things necessary for programming languages  like palindromes      What I m having trouble with is understanding how I can derive all of the above by knowing that regular grammar nonterminals can map to a terminal or a nonterminal followed by a terminal or that a context-free nonterminal maps to any combination of terminals and nonterminals     Can someone help me put all of this together

User · Answer

Regular Expressions    Basis of lexical analysis Represent regular languages   Context Free Grammars    Basis of parsing  Represent language constructs

User · Answer

Regular grammar is either right or left linear  whereas context free grammar is basically any combination of terminals and non-terminals  Hence you can see that regular grammar is a subset of context-free grammar   So for a palindrome for instance  is of the form    S- gt ABA A- gt something B- gt something   You can clearly see that palindromes cannot be expressed in regular grammar since it needs to be either right or left linear and as such cannot have a non-terminal on both side   Since regular grammars are non-ambiguous  there is only one production rule for a given non-terminal  whereas there can be more than one in the case of a context-free grammar

User · Answer

Basically regular grammar is a subset of context free grammar but we can not say Every Context free grammar is a regular grammar  Mainly context free grammar is ambiguous and regular grammar may be ambiguous

User · Answer

A grammar is context-free if all production rules have the form  A    that is  the left side of a rule can only be a single variable  the right side is unrestricted and can be any sequence of terminals and variables   We can define a grammar as a 4-tuple  where V is a finite set  variables     is a finite set  terminals   S is the start variable  and R is a finite set of rules  each of which is a mapping V regular grammar is either right or left linear  whereas context free grammar is basically any combination of terminals and non-terminals  hence we can say that regular grammar is a subset of context-free grammar  After these properties we can say that Context Free Languages set also contains Regular Languages set

User · Answer

Regular grammar - grammar containing production as follows is RG   V- gt TV or VT V- gt T   where V variable and T terminal  RG may be Left Linear Grammar or Right Liner Grammar  but not Middle linear Grammar   As we know all RG are Linear Grammar but only Left Linear or Right Linear Grammar are RG   A regular grammar can be ambiguous   S- gt aA aB A- gt a B- gt a   Ambiguous Grammar - for a string x their exist more than one LMD or More than RMD or More than one Parse tree or One LMD and One RMD but both Produce different Parse tree                   S                   S                                                       a     A             a     B                                                                a                   a   this Grammar is ambiguous Grammar because two parse tree   CFG -  A grammar said to be CFG if its Production is in form      V- gt     where   belongs to  V T     DCFL - as we know all DCFL are LL 1  Grammar and all LL 1  is LR 1  so it is Never be ambiguous  so DCFG is Never be ambiguous   We also know all RL are DCFL so RL never be ambiguous  Note that RG may be ambiguous but RL not   CFL  CFl May or may not ambiguous   Note  RL never be Inherently ambiguous

User · Answer

The difference between regular and context free grammar   N  S  P  S    terminals  nonterminals  productions  starting state Terminal symbols    elementary symbols of the language defined by a formal grammar    abc  Nonterminal symbols  or syntactic variables     replaced by groups of terminal symbols according to the production rules    ABC  regular grammar  right or left regular grammar  right regular grammar  all rules obey the forms   B   a where B is a nonterminal in N and a is a terminal in S B   aC where B and C are in N and a is in S B   e where B is in N and e denotes the empty string  i e  the string of length 0    left regular grammar  all rules obey the forms   A   a where A is a nonterminal in N and a is a terminal in S A   Ba where A and B are in N and a is in S A   e where A is in N and e is the empty string   context free grammar  CFG     formal grammar in which every production rule is of the form V   w    V is a single nonterminal symbol    w is a string of terminals and or nonterminals  w can be empty

User · Answer

I think what you want to think about are the various pumping lemmata  A regular language can be recognized by a finite automaton   A context-free language requires a stack  and a context sensitive language requires two stacks  which is equivalent to saying it requires a full Turing machine    So  if we think about the pumping lemma for regular languages  what it says  essentially  is that any regular language can be broken down into three pieces  x  y  and z  where all instances of the language are in xy z  where   is Kleene repetition  ie  0 or more copies of y    You basically have one  nonterminal  that can be expanded   Now  what about context-free languages   There s an analogous pumping lemma for context-free languages that breaks the strings in the language into five parts  uvxyz  and where all instances of the language are in uvixyiz  for i  ge  0   Now  you have two  nonterminals  that can be replicated  or pumped  as long as you have the same number

User · Answer

a regular grammer is never ambiguous because it is either left linear or right linear so we cant make two decision tree for regular grammer so it is always unambiguous but othert than regular grammar all are may or may not be regular

[context-free-grammar] Regular vs Context Free Grammars

Examples related to context-free-grammar

Examples related to regular-language

Examples related to automata