CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
ContextFree Grammar (CFG)CFG stands for contextfree grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Contextfree grammar G can be defined by four tuples as: G = (V, T, P, S) Where, G is the grammar, which consists of a set of the production rule. It is used to generate the string of a language. T is the final set of a terminal symbol. It is denoted by lower case letters. V is the final set of a nonterminal symbol. It is denoted by capital letters. P is a set of production rules, which is used for replacing nonterminals symbols(on the left side of the production) in a string with other terminal or nonterminal symbols(on the right side of the production). S is the start symbol which is used to derive the string. We can derive the string by repeatedly replacing a nonterminal by the righthand side of the production until all nonterminal have been replaced by terminal symbols. Example 1:Construct the CFG for the language having any number of a's over the set ∑= {a}. Solution: As we know the regular expression for the above language is r.e. = a* Production rule for the Regular expression is as follows: S → aS rule 1 S → ε rule 2 Now if we want to derive a string "aaaaaa", we can start with start symbols. S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa The r.e. = a* can generate a set of string {ε, a, aa, aaa,.....}. We can have a null string because S is a start symbol and rule 2 gives S → ε. Example 2:Construct a CFG for the regular expression (0+1)* Solution: The CFG can be given by, Production rule (P): S → 0S  1S S → ε The rules are in the combination of 0's and 1's with the start symbol. Since (0+1)* indicates {ε, 0, 1, 01, 10, 00, 11, ....}. In this set, ε is a string, so in the rule, we can set the rule S → ε. Example 3:Construct a CFG for a language L = {wcwR  where w € (a, b)*}. Solution: The string that can be generated for a given language is {aacaa, bcb, abcba, bacab, abbcbba, ....} The grammar could be: S → aSa rule 1 S → bSb rule 2 S → c rule 3 Now if we want to derive a string "abbcbba", we can start with start symbols. S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3 Thus any of this kind of string can be derived from the given production rules. Example 4:Construct a CFG for the language L = a^{n}b^{2n} where n>=1. Solution: The string that can be generated for a given language is {abb, aabbbb, aaabbbbbb....}. The grammar could be: S → aSbb  abb Now if we want to derive a string "aabbbb", we can start with start symbols. S → aSbb S → aabbbb
Next TopicDerivation
