Introduction of membership algorithm for CFG

Membership alogithm are used to check whether a string belongs to CFG or not.
If we go with the bruteforce approach then time complexity will be exponential.

So to avoid that we are using CYK algorithm for membership test of a string in CFG

Time Complexity of CYK Algorithm

It is O(|w|³)

Note: where |w| is length of string

---

To proceed with any membership algorithm we have to do the following things to a grammar

1. Elimination of &epsilpn; production
2. Elimination of Unit production
3. Elimination of Useless symbol

---

Note:Follow the order of elimination as given above

---