Context Free Grammar - Automata
Context Free Grammar
Grammar defines a set of rules, and with the help of these rules valid sentences in a language are constructed. A grammar consists of collection of substitution rules, which are also called production rules.
Context Free Grammar have recursive structure. The language that is associated with Context Free Grammar is called Context Free Language. 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 ?.
The variables are those symbols that can be replaced with other variables, terminals, both or ?.
The terminals are those symbols which cannot be replaced by anything.
Example of Context free Grammar:
S -> 0S1
S -> 0
S-> ?
The above given grammar can also be written as:
S -> 0S1|0| ?
If the same variable is given more than one on the left-hand side then we can combine their resulting strings in one line using symbol “|”. The sequence of substitutions for obtaining a string is called derivation.
The reverse substitution is not permitted.
Example: S -> 0 is a production, then we can replace S by 0 but not 0 with S.
Formal Definitions of Context Free Grammar
Context Free Grammar has 4 tuples (V, T, P, S)
V: - V is a finite set of variables also called non-terminals.
T: - T is a finite set of symbols called terminals that form the strings of the language generated by the grammar.
P: - P is a finite set of rules called production rules, each rule have a single variable on the left – hand side and strings of variables and terminals on right hand side.
S: - S is a special symbol called the start symbol.
Let us take some examples of Context Free Grammar
Example1:
Construct Context Free Grammar to generate the following language.
L = {wwR: w ? {0, 1}*}
Solution:
The type of strings that language L generates includes {010010, 110011, 01111110 …..}
Let G = (V, T, P, S) be a context free grammar generating given language
Where V = {S}
T = { 0, 1, ? }
S is the start symbol
P is set of production rules defined as follows:
S -> 0S0
S -> 1S1
S-> ?
Now let us check whether the Context Free Grammar generates the strings that belongs to given language. Consider the string 001100 ? L. The derivations of this string are:
S => 0S0
=> 00S00
=> 001S100
=> 001100
Thus 001100 ? L.
Example 2:
Construct Context Free Grammar to generate the following language.
L = {01(1100) n110 (10) n | n>=0}
Solution:
The type of strings that language L generates includes {01110, 01110011010…..}
Let G = (V, T, P, S) be a context free grammar generating given language
Where V = {S, A, B}
T = {0, 1, ?}
S is the start symbol
P is set of production rules defined as follows:
S -> 01A
A -> 11B0
B -> 00A1
B-> ?
Now let us check whether the Context Free Grammar generates the types of strings that belongs to given language. Consider the string 01110011010 ? L. The derivations of this string are:
S => 01A
=> 0111B0
=> 011100A10
=> 01110011B010
=> 01110011010
Thus 01110011010 ? L.
Example 3:
Construct Context Free Grammar that generates strings over {0, 1} which contains at least four consecutive 0’s.
Solution:
The type of strings that language L generates includes {00001, 110000, 0000, 11010001 …..}
Let G = (V, T, P, S) be a context free grammar generating given language.
Where V = {S, A}
T = {0, 1, ?}
S is the start symbol
P is set of production rules defined as follows:
S -> A0000A
A -> 0A
A -> 1A
A -> ?
Now let us check whether the Context Free Grammar generates the types of strings that belongs to given language. Consider the string 11010001 ? L. The derivations of this string are:
S => A0000A
=> 1A0000A
=> 11A0000A
=> 110A0000A
=> 1101A0000A
=> 11010000A
=> 110100001A
=> 110100001
Thus 110100001 ? L.