Recall that a context-free grammar in normal form is a 4-tuple(V, sigma, R, S)where (a) V is a finite set called the variables. (b) sigma is a finite set, disjoint from V, called the terminals. (c) S elementof V is the start variable. (d) R is a finite set of rules which may be of the following three forms: i. A rightarrow BC ii. A rightarrow a iii. S rightarrow elementof (elementof is the empty string) where a is any terminal and A, B, C are any variables, except that B notequalto S and C notequalto S. If u, v elementof (V U sigma)*, we say that u rightarrow v if there exists a series of applications of rules of R, u = u_1 rightarrow u_2 rightarrow ... rightarrow u_n = v, such that each step u_i rightarrow u_i + 1 consists of replacing some variable in the string u, according to a rule in R. The language generated by the grammar is {u elementof sigma*: S rightarrow u}. A language which can be expressed in this way is known as a context-free language. Show that for any context-free grammar given in the above normal form, there is an algorithm to determine membership in the language generated by the grammar, which runs in time O(n^3) on strings of length n. Recall that a context-free grammar in normal form is a 4-tuple(V, sigma, R, S)where (a) V is a finite set called the variables. (b) sigma is a finite set, disjoint from V, called the terminals. (c) S elementof V is the start variable. (d) R is a finite set of rules which may be of the following three forms: i. A rightarrow BC ii. A rightarrow a iii. S rightarrow elementof (elementof is the empty string) where a is any terminal and A, B, C are any variables, except that B notequalto S and C notequalto S. If u, v elementof (V U sigma)*, we say that u rightarrow v if there exists a series of applications of rules of R, u = u_1 rightarrow u_2 rightarrow ... rightarrow u_n = v, such that each step u_i rightarrow u_i + 1 consists of replacing some variable in the string u, according to a rule in R. The language generated by the grammar is {u elementof sigma*: S rightarrow u}. A language which can be expressed in this way is known as a context-free language. Show that for any context-free grammar given in the above normal form, there is an algorithm to determine membership in the language generated by the grammar, which runs in time O(n^3) on strings of length n