Problem 2: (25 points) Let G-(V,E) be an edge-labeled digraph, where the label of each edge is a sound from a given finite set of sounds =[S1,S2, , s.J. Let Vobe a distinguished node in G. The construct [G,Vol can be viewed as a formal model for speech recognition from a restricted vocabulary. Each path from node vo yields a sequence of sounds made up of the labels of the consecutive edges in the path; the concatenation of the sounds in that sequence is called the label of the path, and corresponds to a word in the restricted vocabulary. Such a path is called a - labeled path. The determination of that word can be dictated by both the actual path and the end node of the path. Note that there could zero, one or more paths from vo having the same label a. Assume that in addition to the sound labels, each edge (x,y) has a non-negative probability p(x,y) of traversing the edge from x to y and producing the corresponding sound. The probability of a path is the product of probabilities of the edges of the path, and represents the probability that the corresponding word is produced by that sound sequence. The most likely word produced by a sound sequencen is the word corresponding to the -labeled path with the highest probability, starting from node Vo a. Write a dynamic programming algorithm that takes as input a model [G,vo,2] (along with the probabilities of the edges) and a sound sequence = where every o-labeled path that begins at node vo; if no b. Problem 2: (25 points) Let G-(V,E) be an edge-labeled digraph, where the label of each edge is a sound from a given finite set of sounds =[S1,S2, , s.J. Let Vobe a distinguished node in G. The construct [G,Vol can be viewed as a formal model for speech recognition from a restricted vocabulary. Each path from node vo yields a sequence of sounds made up of the labels of the consecutive edges in the path; the concatenation of the sounds in that sequence is called the label of the path, and corresponds to a word in the restricted vocabulary. Such a path is called a - labeled path. The determination of that word can be dictated by both the actual path and the end node of the path. Note that there could zero, one or more paths from vo having the same label a. Assume that in addition to the sound labels, each edge (x,y) has a non-negative probability p(x,y) of traversing the edge from x to y and producing the corresponding sound. The probability of a path is the product of probabilities of the edges of the path, and represents the probability that the corresponding word is produced by that sound sequence. The most likely word produced by a sound sequencen is the word corresponding to the -labeled path with the highest probability, starting from node Vo a. Write a dynamic programming algorithm that takes as input a model [G,vo,2] (along with the probabilities of the edges) and a sound sequence = where every o-labeled path that begins at node vo; if no b