FOR FREE CONTENT

Membership algorithm and parsing

Membership algorithm:

To check whether a string ω is in the language (or grammar) L or not i.e. L ∊ ω or L ∉ ω is called membership algorithm. 

Two type of membership algorithm:

1. Brute Force Parsing (BFP)

2. CYK Membership algorithm

1. Brute Force Parsing (BFP): 

In case of Brute Force then there is no intelligence required, it check all cases one by one i.e. it apply all cases one by one. So, time complexity is going to exponential and it became NP – problem.

It takes $\mathbf{O}\mathbf{\left(}{\mathbf{k}}^{\mathbf{n}}\mathbf{\right)}$  where k = Constant and |ω| = n [length of string]

Brute force parsing: Check membership of ω = aaabb is in grammar S → aSb | λ. 

It checks one by one i.e. NP – problem. But to make Brute Force Parsing effective, we have to remove the λ – production and unit production.

2. CYK Membership algorithm:

But when we use CYK as membership algorithm for CFG then complexity will be $\mathbf{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{3}}\mathbf{\right)}$.

CYK algorithm only works on Chomsky Normal Form (CNF) (For details of CNF follow chapter Introduction and Chomsky Normal Form)

So, to apply this algorithm we have to convert CFG to CNF.

CYK Membership algorithm:

1. First remove λ – production, unit production from given CFG
2. Convert new CFG to CNF
3. Apply CYK membership algorithm to CNF

For every context – free grammar, there exist an algorithm (CYK membership algorithm ) that parse any string ω ∊ L(G) in a no. of steps equals to $\mathbf{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{3}}\mathbf{\right)}$ where n = |ω|. 

So, it is also not a linear time parsing algorithm because linear time parsing taking O(n) to parse any string.

But in DCFL we parse in linear time O(n) and LR – grammar exactly corresponds to DCFL, and we know LL and LR grammar complexity is O(n).

LR – LL grammar is always unambiguous.