Coupon Accepted Successfully!


Context Free Languages


A context free language (CFL) is a language generated by a context free grammar (CFG). A CFG is a set of rules for deriving (or generating) strings (or sentences) in a language.

Informally, a CFG consists of:–

— A set of replacement rules, each having a LHS and a RHS.

— Two types of symbols, variables and terminals.

— LHS of each rule is a single variable (no terminals).

— RHS of each rule is string of zero or more variables and terminals.

— A string consists of only terminals.

Formally, a CFG is a 4-tuple (V, Σ, R, S), where

  1. V is a finite set called variables.
  2. Σ is a finite set, disjoint from V, called terminals.
  3. R is a finite set of rules, with each rule being a variable and a string of variables and terminals.
  4. S  V is the start variable.

Chomsky Normal Form

A context free grammar is in Chomsksy Normal Form if every rule is of the form.


A  a

where, a is any terminal and A, B and C are any variables except B and C may not be the start variable. In addition, the rule S ε, where S is the start material is allowed.

Backus Naur Form

An example of a context-free grammar in BNF is given


Push Down Automata


Push Down Automata are like non-deterministic finite automata but have an extra component called a stack. The stack provides additional memory beyond the finite automata provides.

Formally, a push down automata is a 6-tuple (Q, Σ, Γ, δ, q0, F), where

  1. Q is the set of states.
  2. Σ is the input alphabet.
  3. Γ is the stack alphabet.
  4. δ : Q × Σε × Γε  P (Q × Γε) is the transition function.
  5. q0   Q is the start state, and
  6. F  Q is the set of accept states.

Below is the description of PDA that recognizes the language {0n 1n|n ≥ 0}. Let M1 be (Q, Σ, Γ, δ, q1, F), where

Q = {q1, q2, q3, q4}

Σ = {0, 1}

Γ = {0, $} $ = This signifies that stack is empty

F = {q1, q4} and

δ is given by the following table, where in blank entries signify φ.


We can also use a state diagram to describe a PDA, as shown below:–


  • A language is context free if and only if some push down automata recognizes it.
  • Every regular language is context free language.

Pumping Lemma for CFL

If A is a CFL, then there is a number P (the pumping length) where, if S is any string in A of length at least P, then S may be divided into five pieces S = uvwxy satisfying the conditions:–

  1. for each i ≥ 0, uv2wx2y  A,
  2. |vx| > 0, and
  3. |vwx| ≤ P.

Test Your Skills Now!
Take a Quiz now
Reviewer Name