# Define Context Free Grammar & Context Free Language

Context Free Grammar is the important topic of the Theory Of Computation. Theory Of Computation is the Important subject of the Computer.

**Context Free Grammar:**

A context-free grammar is a 4-tuple G=(V, Ʃ, S, P) where,

V is finite set of non-terminals,

Ʃ is disjoint finite set of terminals,

S is an element of V and it’s a start symbol,

P is a finite set formula of the form Aàα where A ∈ V and α∈ (V U Ʃ)*.

**Application of Context-Free Grammar(CFG): **

1) CFG is extensively used to specify the syntax of programming language. 2) CFG is used to develop a parser.

**Context Free Language:**

Language generated by CFG is called context-free language.

Let G= (V, Ʃ, S, P) be a CFG. The Language generated by G is

L(G) : {x ∈Ʃ*/S⟹_{G}* x}

A language L is a context-free Language(CFL) if, there is a CFG G so that L=L(G)

### Write CFG for following: Context Free Grammar

**Write CFG for ab* **SàaX

Xà˄| bX

**Write CFG for a*b* **

SàXY

XàaX|˄

YàbY|˄

**Write CFG for (011+1)*(01)* **

SàAB

Aà011A | 1A | ^

Bà01B | ^

**Write CFG which contains at least three times 1. **

SàA1A1A1A

Aà0A | 1A | ^

**Write CFG that must start and end with same symbol. **Sà0A0 | 1A1

Aà0A | 1A | ^

**The language of even & odd length palindrome string over {a,b} **SàaSa|bSb|a|b|˄

**Moreover, of a and no. of b are same **SàaSb|bSa|˄

**Write CFG for regular expression (a+b)*a(a+b)*a(a+b)* **

SàXaXaX

XàaX|bX|˄

**Write CFG for L={a ^{i}b^{j}c^{k} | i=j or j=k} **

For i=j for j=k

S->AB S->CD

A->aAb | ab C->aC | a

B->cB | c D->bDc | bc

**Write CFG for L={ a ^{i}b^{j}c^{k} | j>i+k} **

SàABC

AàaAb |˄

BàbB | b

CàbCc |˄

**Write CFG for L={ 0 ^{i}1^{j}0^{k} | j>i+k} **

SàABC

Aà0A1 |˄

Bà1B | 1

Cà1C0 |˄

### Define: Regular Grammar

A grammar G=(V, Ʃ, S, P) is regular if every production takes one of the two forms,

BàaC

Bàa

Where B and C are Nonterminals and a is terminal.

**Related Terms**

Theory of Computation, Finite Automata, Union, Intersection & Compliment operation, Pushdown Automata

## Leave a Reply