Decision Problems of CFL

Algorithm To Decide Whether CFL Is Empty Or Not-

 

If we can not derive any string of terminals from the given grammar, then its language is called as an Empty Language. L(G) = ϕ

 

For a given CFG, there exists an algorithm to decide whether its language is empty L(G) = ϕ or not.

 

Algorithm-

 

• Remove all the useless symbols from the grammar.
• A useless symbol is one that does not derive any string of terminals.
• If the start symbol is found to be useless, then language is empty otherwise not.

 

Remember The language generated from a CFG is non-empty iff the start symbol is generating.

 

Example-

 

Consider the following grammar-

S → XY

X → AX

X → AA

A → a

Y → BY

Y → BB

B → b

 

Now, let us check whether language generated by this grammar is empty or not.

 

The given grammar can be written as-

S → aabb

X → aX

X → aa

A → a

Y → bY

Y → bb

B → b

 

Clearly,

• The start symbol generates at least one string (many more are possible).
• Therefore, start symbol is useful.
• Thus, language generated by the given grammar is non-empty.

 

L(G) ≠ ϕ

NOTE-

 

If L(G) = { ∈ } i.e.

• If the language generated by a grammar contains only a null string,
• then it is considered as non-empty.

Algorithm To Decide Whether CFL Is Finite Or Not-

 

For a given CFG, there exists an algorithm to decide whether its language is finite or not.

 

Step-01:

 

Reduce the given grammar completely by-

• Eliminating ∈ productions
• Eliminating unit productions
• Eliminating useless productions

 

Step-02:

 

• Draw a directed graph whose nodes are variables of the given grammar.
• There exists an edge from node A to node B if there exists a production of the form A → αBβ.

 

Now, following 2 cases are possible-

 

Case-01:

 

• Directed graph contains a cycle.
• In this case, language of the given grammar is infinite.

 

Case-02:

 

• Directed graph does not contain any cycle.
• In this case, language of the given grammar is finite.

 

PRACTICE PROBLEMS BASED ON DECIDING WHETHER CFL IS FINITE-

 

Problem-01:

 

Check whether language of the following grammar is finite or not-

S → AB / a

A → BC / b

B → CC / c

 

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

We will draw a directed graph whose nodes will be S , A , B , C.

 

Now,

• Due to the production S → AB, directed graph will have edges S → A and S → B.
• Due to the production A → BC, directed graph will have edges A → B and A → C.
• Due to the production B → CC, directed graph will have edge B → C.

 

The required directed graph is-

 

 

Clearly,

• The directed graph does not contain any cycle.
• Therefore, language of the given grammar is finite.

 

Problem-02:

 

Check whether language of the following grammar is finite or not-

S → XS / b

X → YZ

Y → ab

Z → XY

Solution-

 

Step-01:

 

The given grammar is already completely reduced.

 

Step-02:

 

We will draw a directed graph whose nodes will be S , X , Y , Z.

Now,

• Due to the production S → XS / b, directed graph will have edges S → X and S → S.
• Due to the production X → YZ, directed graph will have edges X → Y and X → Z.
• Due to the production Z → XY, directed graph will have edges Z → X and Z → Y.

 

The required directed graph is-

 

Clearly,

• The directed graph contain cycles.
• Therefore, language of the given grammar is infinite.

CYK Algorithm-

 

CYK Algorithm is a membership algorithm of context free grammar.

 

• It is used to decide whether a given string belongs to the language of grammar or not.
• It is also known as CKY Algorithm or Cocke-Younger-Kasami Algorithm after its inventors.

 

Important Notes-

 

Note-01:

 

• CYK Algorithm operates only on Context Free Grammars given in Chomsky Normal Form.

 

Note-02:

 

• The worst case running time of CYK Algorithm is Θ (n³.|G|).
• Here, n = Length of parsed string and |G| = Size of the CNF Grammar G.

 

Algorithm-

 

Begin

for ( i = 1 to n do )

Vi1 { A | A → a is a production where ith symbol of x is a }

for ( j = 2 to n do )

for ( i = 1 to n - j + 1 do )

Begin

Vij = ϕ

For k = 1 to j - 1 do

Vij = Vij ∪ { A | A → BC is a production where B is in Vik and C is in V(i + k)(j - k) }

End

End

Deciding Membership Using CYK Algorithm-

 

To decide the membership of any given string, we construct a triangular table where-

• Each row of the table corresponds to one particular length of sub strings.
• Bottom most row corresponds to strings of length-1.
• Second row from bottom corresponds to strings of length-2.
• Third row from bottom corresponds to strings of length-3.
• Top most row from bottom corresponds to the given string of length-n.

 

Example-

 

For a given string “x” of length 4 units, triangular table looks like-

 

 

We will fill each box of x_ij with its V_ij.

These notations are discussed below.

 

Notations Used   Notation-01: xij   xij represents a sub string of “x” starting from location ‘i’ and has length ‘j’. Example- Consider x = abcd is a string, then- Number of sub strings possible = n(n+1)/2 = 4 x (4+1) / 2 = 10 We have- x11 = a x21 = b x31 = c x41 = d x12 = ab x22 = bc x32 = cd x13 = abc x23 = bcd x14 = abcd   Notation-02: Vij   Vij represents a set of variables in the grammar which can derive the sub string xij. If the set of variables consists of the start symbol, then it becomes sure- Sub string xij can be derived from the given grammar. Sub string xij is a member of the language of the given grammar.

 

PRACTICE PROBLEM BASED ON CYK ALGORITHM-

 

Problem-

 

For the given grammar, check the acceptance of string w = baaba using CYK Algorithm-

S → AB / BC

A → BA / a

B → CC / b

C → AB / a

Solution-

 

First, let us draw the triangular table.

• The given string is x = baaba.
• Length of given string = |x| = 5.
• So, Number of sub strings possible = (5 x 6) / 2 = 15.

 

So, triangular table looks like-

 

 

Now, let us find the value of V_ij for each cell.

 

For Row-1:

 

Finding V₁₁

 

• V₁₁ represents the set of variables deriving x₁₁.
• x₁₁ = b.
• Only variable B derives string “b” in the given grammar.
• Thus, V₁₁ = { B }

 

Finding V₂₁

 

• V₂₁ represents the set of variables deriving x₂₁.
• x₂₁ = a.
• Variables A and C derive string “a” in the given grammar.
• Thus, V₂₁ = { A , C }

 

Finding V₃₁

 

• V₃₁ represents the set of variables deriving x₃₁.
• x₃₁ = a.
• Variables A and C derive string “b” in the given grammar.
• Thus, V₃₁ = { A , C }

 

Finding V₄₁

 

• V₄₁ represents the set of variables deriving x₄₁.
• x₄₁ = b.
• Only variable B derives string “b” in the given grammar.
• Thus, V₄₁ = { B }

 

Finding V₅₁

 

• V₅₁ represents the set of variables deriving x₅₁.
• x₅₁ = a.
• Variables A and C derives string “a” in the given grammar.
• Thus, V₅₁ = { A , C }

 

For Row-2-

 

RULE As per the algorithm, to find the value of Vij from 2nd row on wards, we use the formula- Vij = Vik V(i+k)(j-k) where k varies from 1 to j-1

 

Finding V₁₂

 

We have i = 1 , j = 2 , k = 1

Substituting values in the formula, we get-

V₁₂ = V₁₁. V₂₁

V₁₂ = { B } { A , C }

V₁₂ = { BA , BC }

∴ V₁₂ = { A , S }

 

Finding V₂₂

 

We have i = 2 , j = 2 , k = 1

Substituting values in the formula, we get-

V₂₂ = V₂₁. V₃₁

V₂₂ = { A , C } { A , C }

V₂₂ = { AA , AC , CA , CC }

Since AA , AC and CA do not exist, so we have-

V₂₂ = { CC }

∴ V₂₂ = { B }

 

Finding V₃₂

 

We have i = 3 , j = 2 , k = 1

Substituting values in the formula, we get-

V₃₂ = V₃₁. V₄₁

V₃₂ = { A , C } { B }

V₃₂ = { AB , CB }

Since CB does not exist, so we have-

V₃₂ = { AB }

∴ V₃₂ = { S , C }

 

Finding V₄₂

 

We have i = 4 , j = 2 , k = 1

Substituting values in the formula, we get-

V₄₂ = V₄₁. V₅₁

V₄₂ = { B } { A , C }

V₄₂ = { BA , BC }

∴ V₄₂ = { A , S }

 

For Row-3-

 

Finding V₁₃

 

We have i = 1 , j = 3 , k = 1 to (3-1) = 1,2

Substituting values in the formula, we get-

V₁₃ = V₁₁. V₂₂ ∪ V₁₂. V₃₁

V₁₃ = { B } { B } ∪ { A , S } { A , C }

V₁₃ = { BB } ∪ { AA , AC , SA , SC }

Since BB , AA , AC , SA and SC do not exist, so we have-

V₁₃ = ϕ ∪ ϕ

∴ V₁₃ = ϕ

 

Finding V₂₃

 

We have i = 2 , j = 3 , k = 1 to (3-1) = 1,2

Substituting values in the formula, we get-

V₂₃ = V₂₁. V₃₂ ∪ V₂₂. V₄₁

V₂₃ = { A , C } { S , C } ∪ { B } { B }

V₂₃ = { AS , AC , CS , CC } ∪ { BB }

Since AS , AC , CS and BB do not exist, so we have-

V₂₃ = { CC }

∴ V₂₃ = B

 

Finding V₃₃

 

We have i = 3 , j = 3 , k = 1 to (3-1) = 1,2

Substituting values in the formula, we get-

V₃₃ = V₃₁. V₄₂ ∪ V₃₂. V₅₁

V₃₃ = { A , C } { A , S } ∪ { S , C } { A , C }

V₃₃ = { AA , AS , CA , CS } ∪ { SA , SC , CA , CC }

Since AA , AS , CA , CS , SA , SC and CA do not exist, so we have-

V₃₃ = ϕ ∪ { CC }

V₃₃ = ϕ ∪ { B }

∴ V₃₃ = { B }

 

For Row-4-

 

Finding V₁₄

 

We have i = 1 , j = 4 , k = 1 to (4-1) = 1,2,3

Substituting values in the formula, we get-

V₁₄ = V₁₁. V₂₃ ∪ V₁₂. V₃₂ ∪ V₁₃. V₄₁

V₁₄ = { B } { B } ∪ { A , S } { S , C } ∪ { ϕ , B }

V₁₄ = { BB } ∪ { AS , AC , SS , SC } ∪ { B }

Since BB , AS , AC , SS , SC and B do not exist, so we have-

V₁₄ = ϕ ∪ ϕ ∪ ϕ

∴ V₁₄ = ϕ

 

Finding V₂₄

 

We have i = 2 , j = 4 , k = 1 to (4-1) = 1,2,3

Substituting values in the formula, we get-

V₂₄ = V₂₁. V₃₃ ∪ V₂₂. V₄₂ ∪ V₂₃. V₅₁

V₂₄ = { A , C } { B } ∪ { B } { A , S } ∪ { B } { A , C }

V₂₄ = { AB , CB } ∪ { BA , BS } ∪ { BA , BC }

Since CB does not exist, so we have-

V₂₄ = { AB } ∪ { BA , BS } ∪ { BA , BC }

V₂₄ = { S , C } ∪ { A } ∪ { A , S }

∴ V₂₄ = { S , C , A }

 

For Row-5-

 

Finding V₁₅

 

We have i = 1 , j = 5 , k = 1 to (5-1) = 1,2,3,4

Substituting values in the formula, we get-

V₁₅ = V₁₁. V₂₄ ∪ V₁₂. V₃₃ ∪ V₁₃. V₄₂ ∪ V₁₄. V₅₁

V₁₅ = { B } { S , C , A } ∪ { A , S } { B } ∪ { ϕ } { A , S } ∪ { ϕ } { A , C }

V₁₅ = { BS , BC , BA } ∪ { AB , SB } ∪ { A , S } ∪ { A , C }

Since BS , SB , A , S and C do not exist, so we have-

V₁₅ = { BC , BA } ∪ { AB } ∪ ϕ ∪ ϕ

V₁₅ = { S , A } ∪ { S , C } ∪ ϕ ∪ ϕ

∴ V₁₅ = { S , A , C }

 

Now,

• The value of V_ij is computed for each cell.
• We observe V₁₅ contains the start symbol S.
• Thus, string x₁₅ = baaba is a member of the language of given grammar.

 

After filling the triangular table, it looks like-

 

 

Results From Triangular Table-

 

The following important results can be made from the above triangular table-

 

Result-01:

 

• There exists total 4 distinct sub strings which are members of the language of given grammar.
• These 4 sub strings are ba, ab, aaba, baaba.
• This is because they contain start symbol in their respective cell.

 

Result-02:

 

• Strings which can not be derived from any variable are baa, baab.
• This is because they contain ϕ in their respective cell.

 

Result-03:

 

• Strings which can be derived from variable B alone are b, aa, aba, aab.
• This is because they contain variable B alone in their respective cell.