19 CFG
19 CFG
19 CFG
Learning Outcomes: At the conclusion of the chapter, the student will be able to:
• Identify whether a particular grammar is context-free
• Construct context-free grammars for simple languages
• Produce leftmost and rightmost derivations of a string generated by a context-free
grammar
• Construct derivation trees for strings generated by a context-free grammar
A Regular Grammar (RG) is either left linear or right linear. Left linear grammar is one in which
ALL productions are of the following form:
A→x
A → Bx, A, B V and x T*
Right linear grammar is one in which ALL productions are of the following form:
A→x
A → xB, A, B V and x T*
The productions of Regular Grammars are restricted in two ways
1. Left side must be a single variable
2. Right side must have a special form.
By retaining the first restriction and permitting anything on the right side, we get Context Free
Grammars (CFG). Many useful languages are not regular. Context-free grammars are very useful
for the definition and processing of programming languages. A context-free grammar has no
restrictions on the right side of its productions, while the left side must be a single variable
19.1 Definition of CFG
A grammar CFG G is defined by a quadruple
G = (V, T, S, P) where
Note that every Regular Grammar is Context Free. However, vice versa is not true.
1 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
2 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
3 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
E * E
( E ) I
E + E
1
I
I I
a b
4 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
The relationship between the number of leading a’s and trailing d’s in the language indicates that
the recursive rule is needed to generate them. The same is true for b’s and c’s. Derivations in the
grammar generate strings in an outside-to-inside manner. The S rules produce the a’s and d’s
while the A rules generate b’s and c’s. The rule A → bc, whose application terminates the
recursion, ensures the presence of the substring bc in every string in the language.
Example 19.9
Find a CFG that generates the language
L(G) = { an bm | 0 ≤ n ≤ m ≤ 2n}.
Solution
S → aSb | aSbb | ε
The first recursive rule of G generates a trailing b for every a, while the second generates two
b’s for each a. Thus there is at least one b for every a and at most two, as specified in the
language.
Example 19.10
Consider the grammar
S → abScB | λ
B → bB | b
What language does it generate?
Solution
The recursive S rule generates an equal number of ab’s and cB’s. The B rules generate b+. In a
derivation, each occurrence of B may produce a different number of b’s. For example in the
derivation
S ⇒ abScB ⇒ ababScBcB ⇒ ababcBcB ⇒ ababcbcB ⇒ ababcbcbB ⇒ ababcbcbb, the first
occurrence of B generates a single b and the second occurrence produces bb. The language of the
grammar consists of the set L(G) = { (ab)n (cbm)n | n ≥ 0, m > 0}.
Example 19.11
Construct context free grammars to accept the following languages. Consider Σ = {0, 1}
a) {w | w starts and ends with the same symbol}
Solution
S → 0A0 | 1A1
A → 0A | 1A | ε
b) {w | |w| is odd}
Solution
S → 0A | 1
A → 0S | 1S | ε
5 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
6 Seema Shukla
Context Free Grammars
KCS- 402 Theory Of Automata and Formal Languages
Example 19.15
Construct CFGs for the following languages
1) L = {a,b}+
S → aS | bS | a | b
2) L = {anbman | n ≥ 1, m ≥ 0}
S → aSa | aAa
A → bA | ε
3) L = { (ab)n | n ≥ 0}
S → abS | ε
4) L = { w | na(w) = nb(w) }
S → SS | aSa | bSb | ε
5) L = {anbmcn+m | n,m ≥ 0}
S → aSc | A
A → bAc | ε
6) L = { {anbm | n ≠ m }
S → AS1 | S1B
S1 → aS1b | ε
A → aA | a
B → bB | b
7 Seema Shukla