4. 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. We also allow an expression for the empty set of strings. 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 = {xy | S, y T}. Finally, if S is a subset of strings already known to be expressible, there is a particularly powerful expressionary device that allows you to express the following (possibly infinite set of strings) which are the concatenations of an arbitrary number (zero or more) strings from S: S*= {e, 81, 81 82, 81 82 83, 8182. Sn,... n 0, all si S}, where $1,82,... S (they are not necessarily distinct, i.e., repetitions are allowed), and 81 82 denotes the concatenation of $1 and 82, and similarly for $182... Sn. Now suppose we are given a 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}.)