Intro to Theory of Computation

Trist1111

Ch6CYKv20.pptx

Home >Computer Science homework help >Intro to Theory of Computation

Parsing Algorithms

The CYK Algorithm

The membership problem:

Problem:

Given a context-free grammar G and a string w

G = (V, T ,P , S) where

V finite set of variables

T (the alphabet) finite set of terminal symbols

P finite set of rules

S start symbol (distinguished element of V)

V and T are assumed to be disjoint

Question: Is w in L(G)?

The CYK Algorithm Basics

The grammar must be in a Chomsky Normal Form.

Uses a “dynamic programming” or “table-filling algorithm”

CYK Algorithm

Let G = (V,T,S,P) with T ={a, b}

V = { S, A, B, T, X} and P defined below

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

And let w = aaabbb. Is wL(G)?

i \ j	1	2	3	4	5	6
1	a
2		a
3			a
4				b
5					b
6						b

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

w on the diagonal

i \ j	1	2	3	4	5	6
1	A
2		A
3			A
4				B
5					B
6						B

Strings length 1

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A	
2		A	
3			A	S, T
4				B	
5					B	
6						B

Strings length 2

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A		
2		A	
3			A	S, T
4				B	
5					B	
6						B

Strings length 3

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A		
2		A		X
3			A	S, T
4				B	
5					B	
6						B

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

W = aaabbb

Strings length 3

i \ j	1	2	3	4	5	6
1	A		
2		A		X
3			A	S, T	
4				B	
5					B	
6						B

Strings length 3

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A		
2		A		X
3			A	S, T	
4				B		
5					B	
6						B

Strings length 3

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A			
2		A		X
3			A	S, T	
4				B		
5					B	
6						B

Strings length 4

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A			
2		A		X	S, T
3			A	S, T	
4				B		
5					B	
6						B

Strings length 4

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A			
2		A		X	S, T
3			A	S, T		
4				B		
5					B	
6						B

Strings length 4

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A				X
2		A		X	S, T
3			A	S, T		
4				B		
5					B	
6						B

Strings length 5

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A				X
2		A		X	S, T	
3			A	S, T		
4				B		
5					B	
6						B

Strings length 5

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A				X	S, T
2		A		X	S, T	
3			A	S, T		
4				B		
5					B	
6						B

Strings length 5

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

i \ j	1	2	3	4	5	6
1	A				X	S, T
2		A		X	S, T	
3			A	S, T		
4				B		
5					B	
6						B

Strings length 5

S -> AB | XB

T -> AB | XB

X -> AT

A -> a

B -> b

w = aaabbb

Therefore:

Time Complexity:

The CYK algorithm can be

easily converted to a parser

(bottom up parser)

Observation:

aaabbb L(G)

O(|w|3)

Example 2

Consider the CNF grammar G = (V,T,S,P) where

V = {S, A, B, C, D }, T = { a, b, c }, S = S and P is given below.

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

Use the CYK to determine if the strings w1 = acbb and w2 = bbca are in the language L(G). If the string is in L(G) construct the parse tree.

i \ j	1	2	3	4
1	a
2		c
3			b
4				b

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w1 = acbb

i \ j	1	2	3	4
1	A	S,A,C
2		C	C
3			B,C	B, C
4				B,C

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w1 = acbb

i \ j	1	2	3	4
1	A	S,A,C	S,A,C
2		C	C	C
3			B,C	B, C
4				B,C

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w1 = acbb

i \ j	1	2	3	4
1	A	S,A,C	S,A,C	S, A, C
2		C	C	C
3			B,C	B, C
4				B,C

Yes

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w1 = acbb

i \ j	1	2	3	4
1	b
2		b
3			c
4				a

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w2 = bbca

i \ j	1	2	3	4
1	B, C
2		B, C
3			C
4				A

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w2 = bbca

i \ j	1	2	3	4
1	B, C	B, C
2		B, C	B, C
3			C	
4				A

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w2 = bbca

i \ j	1	2	3	4
1	B, C	B, C	B, C
2		B, C	B, C	
3			C	
4				A

w on the diagonal

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w2 = bbca

i \ j	1	2	3	4
1	B, C	B, C	B, C	
2		B, C	B, C	
3			C	
4				A

No not in the language

S AB | AC

A  AC | AB | a

B  BB | BC | b

C  AC | CC | c | b

w2 = bbca

Theorem

The CYK Algorithm correctly computes X i j for all i and j; thus w is in L(G) if and only if S is in X1n.

The running time of the algorithm is O(|w|3|P|), where |P| is the number of productions in the grammar, we can assume this is a constant.

O(w2) cells in the table, O(w) to fill in each cell.

Question

Show the CYK Algorithm with the following example:

CNF grammar G

S  AB | BC

A  BA | a

B  CC | b

C  AB | a

w is ababa

Question Is ababa in L(G)?

Basics of CYK Algorithm

The Structure of the rules in a Chomsky Normal Form grammar

Uses a “dynamic programming” or “table-filling algorithm”

Complexity O(|w|3)