Graded Problem (Page limit: 1 sheet; 2 sides) Suppose you have been shown a new programming language that allows you to express the following: Any single symbol in the English alphabet set {A, B,..., Z} is expressible. These are considered strings of length 1. A special expression e also exists that denotes the empty string. Given some two expressions that can express some two subsets S and T of strings, you can form an expression that expresses its union SUT. its concatenation S . T = {ry | x S, y E T). Finally, if s is a subset of strings already known to be expressible, there is a particularly powerful expressionery device that allows you to express the following (possibly infinite set of strings) S* = fe,81,s182 , . . . ,8182 n , . . . I si es), where s1,82,... E S (they are not necessarily distinct, i.e, repetitions are allowed), and s182 denotes the concatenation of 81 and s2, and similarly for 8182n. Now suppose we are given directed graph of n vertices, where every (directed) edge is labeled by one or more of the letters in (A, B,..., Z). Use the idea of Dynamic Programming to show that an expression can be found in this programming language that expresses the set of all string that would lead a path from vertex 1 to vertex n. Hint: First show that you can express the subset of such paths from any i to any j that does not pass through any vertex. Then consider all paths from i to j that pass through vertices among {1,...,k]. Graded Problem (Page limit: 1 sheet; 2 sides) Suppose you have been shown a new programming language that allows you to express the following: Any single symbol in the English alphabet set {A, B,..., Z} is expressible. These are considered strings of length 1. A special expression e also exists that denotes the empty string. Given some two expressions that can express some two subsets S and T of strings, you can form an expression that expresses its union SUT. its concatenation S . T = {ry | x S, y E T). Finally, if s is a subset of strings already known to be expressible, there is a particularly powerful expressionery device that allows you to express the following (possibly infinite set of strings) S* = fe,81,s182 , . . . ,8182 n , . . . I si es), where s1,82,... E S (they are not necessarily distinct, i.e, repetitions are allowed), and s182 denotes the concatenation of 81 and s2, and similarly for 8182n. Now suppose we are given directed graph of n vertices, where every (directed) edge is labeled by one or more of the letters in (A, B,..., Z). Use the idea of Dynamic Programming to show that an expression can be found in this programming language that expresses the set of all string that would lead a path from vertex 1 to vertex n. Hint: First show that you can express the subset of such paths from any i to any j that does not pass through any vertex. Then consider all paths from i to j that pass through vertices among {1,...,k]