retagged by
2,773 views

2 Answers

Best answer
5 votes
5 votes

i) $w= aabb$

$x_1= a,\;x_2=a,\;x_3=b,\;x_4=b$

string derived from Production(s)
$x_1$ $A$
$x_2$ $A$
$x_3$ $B$
$x_4$ $B$

 

String derived from Production(s)
$x_1x_2$ -
$x_2x_3$ $S,B$
$x_3x_4$ $A$

 

String derived  from Production(s)
$x_1x_2x_3$ $S,B$
$x_2x_3x_4$ $A$

 

String derived from Production(s)
$x_1x_2x_3x_4$ $A$

Strings $x_1x_2x_3x_4$, i.e, $w=aabb$ cannot derived from S, So $aabb$ do not belong to $L(G)$

Apply same procedure to other strings. 

selected by
1 votes
1 votes

CYK Algorithm is used to check the  Membership property of CFG . means to check whether w ∊ L(G) or not. It is of $O(n^{3})$

Before Applying CYK Algorithm Make sure your Grammer is in CNF

case 1 : aabb

case 2: bbab

References

edited by

Related questions

1 votes
1 votes
0 answers
1
4 votes
4 votes
1 answer
2
Shefali asked Nov 8, 2015
1,626 views
0 votes
0 votes
1 answer
3
Supromit Roy asked Jan 8, 2015
1,080 views
cyk algorithm is used for CFG'S to test which class of problem???
0 votes
0 votes
2 answers
4
admin asked Mar 30, 2020
1,658 views
Let $n$ is the length of string to test for membership, then the number of table entry in CYK algorithm is$n(n+1)$$n^2+1$$n^2-1$$n(n+1)/2$