Let {a,b} and s E E' be a string of length n with n > 0. Denote by N.(s) the number of times that a appears in s. Let d(s) = N.(8) - Ny(s). If d(s) = 0 and for any prefix p of * N.(P) 2 N.(p), then s is balanced. (You may think of "a" as a left parenthesis"" and "b" as a right parenthesis ")" for balanced parentheses.) Note that dry)=d(x) + d(y) for all 1, y EE. In the following statements, select all that are correct If a string & * is balanced, then either 1.5 the empty string); or 2. ry, where re and x and y are balanced; or 3.- ab, where z is a balanced string, Given ifs - then N.(s) = N() == 0. Thus, d(s) = 0. Let p be any prefix of s, then p=c. Hence, N.C) - N.). This implies that the empty string is balanced The empty string cannot be balanced because it does not have prefix Od Assume that s is balanced and not empty. Then & cannot start with a b. This can be proven by contradiction: Suppose s = 68'. Let p = b. Then N.(p) = 0 and N. (p) = 1. That is, N.(p) 0. A contradiction. Assume that is balanced and not empty. Then must begin with an a and end with 3. Lat be the shortest prefix of with d(x) = 0. Then r is balanced. This can be shown as follows for any prefix p of, it's also a prefix of s, and so N.) NC). Thus, is balanced. If | No(ap), for otherwise if N.(ap) N. (ap) for some such p, then r=ap is the shortest balanced prefix of s, which violates the assumption. Thus, N.(ap) - 1 N.(ap). Since N.P) = N.(ap) - 1, we have N.C) No (ap) N. (p). Hence, 2 is balanced Assume that is balanced and not empty. Then must begin with an a and end with a 6. Let be the shortest prefix of with d(x) = 0. Then is balanced. This can be shown as follows for any prefix p of 2, it's also a prefix of, and so N.) 2 NO). Thus, in balanced. Ifx-1 with ab, and can we conclude that is also balanced? Since d() d(a) + d(s) + d(b) and (s) - 0, where d(a) = 1 and (b) --1, we have(s) - 0 However, for some non-empty prefix pofs, it is posible that .(P)