4. Suppose you have been shown a new programming language that allows you to express the...

Transcribed Image Text:

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}.) 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}.)

Answer rating: 100% (QA)

To express the subset of paths from any vertex i to any vertex j that does not pass through any vertex we can use the expressionary device mentioned in the prompt to express the concatenation of an ar... View the full answer