Theory of Computation – Context Free Grammars (CFG) and Context Free Languages (CFL)

There are four important components in a grammatical description of a language:

1. There is a set of symbols that form the strings of the language being defined. They are called terminal symbols, represented by V_t.
2. There is a finite set of variables, called non-terminals. These are represented by V_n.
3. One of the variable represents the language being defined; it is called the start symbol. It is represent by S.
4. There are finite set of rules called productions that represent the recursive definition of a language. Each production consists of:
   1. A variable that is being defined by the production. This variable is often called the head of the production.
   2. The production symbol ->.
   3. A string of zero or more terminals and variable.

Formal definition

A context-free grammar (CFG) is a 4-tuple G=(V_n, V_t, S, P), where V_n and V_t are disjoint finite sets, S is an element of V_n, and P is a finite set of formulas of the form A -> α, where A ϵ V_n and α ϵ (V_n U V_t)*.

Iterative Derivation

If α -> β is a production of P in CFG and a and b are strings in (V_n, V_t)*, then
Aαb =>_G aβb
We say that the production α -> β is applied to the string aαb to obtain aβb or we say that aαb directly drives aβb.
Now suppose α₁, α₂, α₃, …., α_m are string in (V_n U V_t)*,
m >= 1 and α₁ =>_G α₂, α₂ =>_G α₃, …., α_m-1 =>_Gα_m
Then we say that α₁ =>_G^* α_m, i.e. , we say α₁, derives α_m in grammar G. If α derives β by exactly i steps, we say α=>_Gⁱ β.

The Language Generated by a CFG

Let G = (V_n, V_t, 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).

Bacos Naur Form (BNF)

CFGs are generally written in BNF. In this notation we combine multiple productions with same non-terminal on the left hand side as follows:
S -> bA/aB

Note: We always begin with the start symbol S.

Example:Write a CFG for the language
L = {wcw^r | w ϵ (a, b)*}
Solution

Eample 2: Write a CFG for the regular expression r = 0*1(0+1)*
Solution

Question 1: Write a CFG, which generates palindrome for binary numbers.
Solution

Question 2: Write a CFG for language L = {0ⁱ1^j2^k | k <= i or k <= j}
Solution

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.