Chomsky Normal Form | TOC

CYK Algorithm :

CYK algorithm is used to check is accepted by any context free grammar or not.

CYK stands for Choche's Yonger's applied on that CFG which is Chomsky Normal Form.

Example 1:

    S → AB | BC

    A → BA | a

    B → CC | b

    C → AB | a

Using CYK method find the validity of the following string.

1. baaba

Solution:

STEP 1: 

We have  five character in a string , so we first make five columns and place each character in individual column in first row.

From above grammar we know that    B → b  ,  A,C → a

STEP 2:

Now concatenate the two consecutive character from string and put it into separate column in second row.

Working Note:

For row 2 , col 1

For row 2 , col 2

Note, if any production not exist then write φ

For row 2 , col 3

For row 2 , col 4

Step 3:

Now concatenate the three consecutive  character from string and put it into separate column in third row.

Working Note:

Step 4:

Now concatenate the four consecutive character from string and put it into separate column in forth row.

Working Note:

Step 5:

Now concatenate the five consecutive character from string and put it into separate column in fifth row.

Working Note:

Now we check whether final cell or 5th row contain starting symbol (S) or not .If final cell contain starting symbol the string is accepted otherwise string is rejected.

Hence given string (baaba) is accepted.

Example 2: 

    S → AB | BC

    A → BA | a

    B → CC | b

    C → AB | a

Using CYK method find the validity of the following string.

1. aaaaa

2. aaaaaa