Context Free Language Tutorial Notes Study Material with Examples

What is Context-Free Language

In formal Language theory, a context-free language is a language generated by some context free grammar. The set of all context- free languages is identical to the set of language accepted by pus-down automata.

Finite automata accept all regular language. Many simple language are non-regular and there is no finite automata that accepts them.

e.g. The non-regular language are like

{aⁿ bⁿ : n = 0, 1, 2, …..}

{w w^R : w ϵ {a, b} * }

Context-free language are a larger class of language that encompasses all regular language and many others, including the two above. But reverse is not true i.e. , every context-free language is not necessarily regular.

what is Context-Free Grammar (CFG)

A context-free grammar is defined as 4-tuples (Ʃ, V_n , P, S),

Where, Ʃ is an alphabet (each character is Ʃ is called terminal).

V_n is a set of non-terminals.

P is the set of production rules, where every production has the form

A → α : where, A ϵ V_n, α ϵ (V_n, U Ʃ)*

e.g.  Here is a formal CFG for { 0ⁿ 1ⁿ : n ≥  1}

Terminals={0, 1}

Non-terminales={S}

Start symbol= S

Productions = S →0 ,1 ; S → 0 S 1

Note: The Language which are generated by context-free grammars are called Context-Free Language (CFL)

What is Derivations

A derivation of a string is a sequence of rule applications. The Language defined by a context-free grammar is the set of strings derivable from the start symbol S (for Sentence).

Definition

If v is one-step derivable from u, written u => v. If v is derivable from u, written u*_=> if there is a chain of one derivations of the form.

u => u₁ => u₂  => v

e.g. , Consider the context free grammar

G=({s}, {0,1}, P, S)

Productions

1. S →0S1 or just only S →0S1/^
2. S → ^

Derivations are

1. S => 0S1 using (i)

=>0 1 using (ii)  S => ϵ (2)

1. S=>0S1 using (i)

=>00S 11 using (i)

=> 000S 111 using (i)

=> 000 111 using (ii)

Derivation Tree

A derivation Tree (or Parse Tree) can be defined with any non-terminal as the root, internal nodes are non-terminals and leaf nodes are terminals. Every derivation corresponds to one derivation tree.

If a vertex A has k children with labels A_1, A_2, A_3, …….A_k , then A →   A₁ A₂ A_3….. A_k will be a production in context-free grammar G.

e.g.                 S → AB

A → aAA

A → aA

B → bB

B → b

 

---

Derivation of a String

• Every Derivation corresponds to one derivation Tree.

S => AB

=> aAAB

=> aaAB

=> aaab

• Every Derivation tree corresponds to one or more derivations.

S => AB     S => AB     S => AB

=> aAAB    => Ab        => AB

=> aaAB     => aAAb    => aAAb

=> aaab     => aaab     => aaab

---

Left Most Derivation and Right Most Derivation

A derivation is left most (right most), if at each step in the derivation a production is applied to the left most (right most) non-terminal in the sequential form. In above three derivations, the first one is. Left most derivation and the second one is right most derivation, the third is neither.

Ambiguous Grammar

A context-free grammar G is ambiguous if there is at least on string in L(G) having two or more distinct derivation tree (or equivalently, two or more) distinct left most derivations or two or more distinct right most derivations).

Because C does not produce terminal symbols so this production will be deleted. Now the modified productions are

S → aS | A

A ––→ a

B → aa

Step 2  Identity the various dependency graph

S → AB

In this graph, B variable is not reachable from S so it will be deleted also. Now the productions are S → aS | A

A → a

Eliminate Null Productions

If any variable goes to ^ then that is called as nullable variable.

e.g., A → ^, then variable A is said to be nullable variable

Step1 Scan the nullable variable in the given production list.

Step2 Find all productions which does not include null productions.

P^ = p (null productions)

e.g. consider the CFG has following productions-

S → A B a C

A → B C

B → b | ^

C → D | ^

D → d

Solve step find the nullable variable firstly the set is empty

N = {}

N = {B, C}

N= {A, B, C}

Due to B, C variable,

A will also be a nullable variable

Step 3  P^ = p (null productions)

S → B a C | A a C | A B a | a C | B a | Aa | a

A → B | C

B → b

C →    D

D → d

The above grammar is the every possible combination except ^

Now put this grammar with original grammar with null.

S → AB a C | Ba C | AaC | ABa | aC | Ba | Aa | a

Eliminate the Unite-productions

A production of the type A → B, where A, B are variable is called unit productions.

Step 1 Using productions, we create dependency graph

 

S =>* B

S =>^* B & B =>^* A

S =>^* A

Step 2 Now the production without unit productions

S → AB                                                          S → bb | a | bc

B → b                         +                      A → bb

A → B | C                                                      B → a | bc

Now the final grammar is

S → Aa|bb|a|bc

B → bb|a|bc

A → a | bc |bb

Normal Forms of CFGs

Ambiguity is the undersirable  property of a context-free grammar that we might wish to eliminate. To convert a context-free grammar into normal form, we start by trying to eliminate null productions of the form A → ^ and the unit productions of the form B → C.

There are Two normal forms.

1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)

Chomsky Normal Form (CNF)

A context-free grammar G is said to be in Chomsky Normal Form, if every production is of the form either A → a, (exactly a single terminal in the right hand side of the production) of A → BC (exactly two variable in the right hand side of production).

e.g. ,the context-free grammar G with productions S → AB, A → a, B → b is in Chomsky normal form.

Chomsky Normal Form Properties

• The number of steps in derivation of any string ω of length n is 2n-1, where the grammar should be in CNF.
• The minimum height of derivation tree of any ω of length n is

┌ log₂ n┐+ 1.

• The maximum heigth of derivation tree of any ω of length n = n.

 Greibach Normal Form (GNF)

A context-free grammar is said to be is Greibach Normal Form, if every production is of the form

A → aα

Where,          a ϵ Ʃ A ϵ V_N  and  α ϵ V_N^*

Decision Algorithms for CFLs

Theorem There are algorithms to determine following for a CFL L/\

Empty is there any word in L?

Finite is L finite?

Membership For a particular string ω is ω ϵ L?

Pumping Lemma for CFLs

The Pumping lemma is used to prove that certain languages are not CFL.

Closure Properties of CFLs

CFLs are closed under following properties

• Union
• Concatenation
• Kleene Closure
• Substitution
• Reverse Homomorphism
• Homomorphism

CFLs is not closed under following properties

• Intersection
• Complementation

Deterministic Context-Free Language (DCFL)

The set of Deterministic Context-Free Language is a proper subset of the set of context-free languages that posses an unambiguous context-free grammar.

Key Points

• The problem of whether a given context-free language is deterministic is undividable.
• Deterministic Context-Free Language can be recognized by a deterministic turning machine in polynomial time and O (log²n) space.
• The language of this class have great practical importance in computer science as they can be passed much more efficiently then non deterministic Context-Free Language.

---

Pushdown Automata Tutorial Notes Study Material with Examples

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

Learn Pushdown Automata in Handbook Series:  Click here