Mathematical Foundation of Computer Science

DHARM

284 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

B

a

S

a

a

{A,qf}

Fig. 11.8

11.5CONTEXT FREE GRAMMARS (CFG)/(TYPE-2 GRAMMAR) AND CONTEXT

FREE LANGUAGES (CFL)

As we see earlier, that a grammar G = (VN, VT, S, P) is said to be context free grammar if P
contains the production of type α → β, i.e.,
l α must be a single non terminal, and
l | β| ≥ | α |.
For the case that if ε be in the language of the grammar G then S → ε is also a production
is in set P exceptionally.
And the language generated by context free grammar G is context free language that is
L(G) where,

L(G) = {x ∈ VT*/S ⇒N x}

Solve the examples of CFGs and CFLs

Example 11.5. If a language L = {ak bk/k ≥ 1} then L is CFL. Prove it.

Sol. Since L is CFL if and only if it generates from CFG. So, try to find the Grammar G i.e.

L = L (G).

where L = {ab, aabb, aaabbb, ..........}

Let the grammar G = (VN, VT, S, P) where,

VT = {a, b}, VN = {S, A ....select arbitrary symbols as per the requirements}, S is the

starting symbol and set of productions are determined as follows:

l Since L contains string ‘ab’ hence productin will be,

S → ab

l For the next strings there is a recursive iterations of string ‘a S b’ so production will

be,

S → a S b

Using productions S → ab | a S b we can derive all the strings of L such as,

S ⇒ ab,

S ⇒ a S b ⇒ a a b b.

S ⇒a S b ⇒ a a S b b ⇒ a a a b b b and so on.

Hence L(G) = L and since there is no further need of the non terminal symbols hence VN

contains only symbol S.

So, G = ({S}, {a, b}, S, { S → a b | a S b }) is the required grammar.

Since, both productions fulfill the restrictions. Hence G is a CFG and language L is CFL.

Example 11.6. Prove that Language L = {ak bk cl/k ≥ 1 and l ≥ 1} is a CFL.
Proof. We will Construct the grammar G for the language L i.e. L = L(G)
Now, we see that in the language L,