[go: up one dir, main page]
Scribd
Upload
162 views3 pages

Addis Ababa University College of Natural and Computational Science

The document discusses the Cocke-Younger-Kasami (CYK) algorithm, which is a dynamic programming algorithm for parsing context-free grammars. It works by constructing a triangular table where each row corresponds to substring lengths and cells contain the nonterminals that could generate that substring based on splits of the string. The algorithm fills the table by comparing pairs of previously computed sets to determine possible splits and the nonterminals that could generate them. An example is given to demonstrate how the algorithm would determine if a string is in the language of a given grammar by checking for the start symbol in the bottom right cell of the filled table.

Uploaded by

Dawit Birhanu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
162 views3 pages

Addis Ababa University College of Natural and Computational Science

The document discusses the Cocke-Younger-Kasami (CYK) algorithm, which is a dynamic programming algorithm for parsing context-free grammars. It works by constructing a triangular table where each row corresponds to substring lengths and cells contain the nonterminals that could generate that substring based on splits of the string. The algorithm fills the table by comparing pairs of previously computed sets to determine possible splits and the nonterminals that could generate them. An example is given to demonstrate how the algorithm would determine if a string is in the language of a given grammar by checking for the start symbol in the bottom right cell of the filled table.

Uploaded by

Dawit Birhanu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Addis Ababa University College of natural and

computational science
Formal Language and Automata Theory assignment

Prepared by:

1. Bezawit Asfaw NSR/9837/10

Submitted to: Teacher Mekonnen G


What is cyk algorithm
Cocke-Younger-Kasami algorithm a dynamic programming algorithm – partial solutions are
stored and efficiently reused to find all possible parses for the entire sentence. also known as
the CKY algorithm (CYK or CKY) is a highly efficient parsing algorithm for context-free grammars

The algorithm

if a string s ∈ L(G), then there exists a production in the CNF grammar G such that A → BC,
where B is a nonterminal that generates some prefix of s, and C is a nonterminal that generates
the rest. To restate that in the bottom-up fashion befitting of a dynamic programming
algorithm: given a string s, consider any “split” `, r such that ` + r = s. (So, if s = 10001, then one
such split is ` = 10 and r = 001.) We assume we know all the nonterminal that can generate ` and
all the nonterminal that can generate r. To determine the nonterminal that generate s, see if
there is a nonterminal called B that generates `, a nonterminal C that generates r, and a
nonterminal A that generates BC. In that case, we know that A generates s.

-> Construct a triangular table

-> each raw corresponds to one length of substring

-> Xi, i is the set of variables A such that A->wi is a production of G

-> Compare at most n pairs of previously computed sets: (Xi, i , Xi+1, j ), (Xi, i+1 , Xi+2, j ) … (Xi, j-1 , Xj, j

Purpose

->Determine context free grammar membership


->Regular expression in python

Its application:

-> A lot of language-based task.


-> Reconstructing a task hierarchy after observing a trace. For example you track where
someone car has been all day on map
First they went to work, but all the way to work made a detour, probably to avoid traffic
jam after work they stopped at store, then went to visit a friend, and then went to
home, but took a small detour to get gas.cyk would give the probability of the above
explanation, compared tofor example: first the person drove to intersection X. Then
they drove to intersection Y, making seven hours stop at work.
How dose the cyk algorithm work?

Example let our grammar G be:

S-> AB| BC

A-> BA| a

B->CC |b

C->AB |a

Check if baaba is in L(G):

1. Insert single length rules into a table

B a A B A
B {B}
A {A,C}
A {A,C}
B {B}
A {A,C}

2.We then fill the remaining cells of our table.


B a A b A
B {B} {S,A} - - {S,A,C}
A {A,C} {B} {B} {S,A,C}
A {A,C} {S,C} {B}
B {B} {S,A}
A {A,C}

We observe that s in the cell(1,5) hence ,the string baaba belongs to L(G).

You might also like