FLAT

 Context-Free Grammar (CFG) 

CFG stands for context-free grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as: 

1. 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 non-terminal symbol. It is denoted by capital letters. 

P is a set of production rules, which is used for replacing non-terminals symbols(on the left side of the production) in a string with other terminal or non-terminal 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 non-terminal by the right-hand side of the production until all non-terminal 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 1. r.e. = a*

Production rule for the Regular expression is as follows: 

1. S → aS rule 1 

2. S → ε rule 2 

Now if we want to derive a string "aaaaaa", we can start with start symbols. 

1. S 

2. aS 

3. aaS rule 1 

4. aaaS rule 1 

5. aaaaS rule 1 

6. aaaaaS rule 1 

7. aaaaaaS rule 1 

8. aaaaaaε rule 2 

9. 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 → ε