PROBLEM 1: Write a function count that computes the number of strings w of length n over a, b, c with the following property: In any substring of length 4 of w, all three letters a, b and c occur at least once. For example, strings like abbcaabca satisfy the property, but a string like bacaabbcabac does not satisfy the property since the substring aabb does not have a c. The idea is to create a DFA M for the language Lwin any substring of length 4 of w, all three letters a, b and c occur) Suppose M-Q. 6,0,F) states. Assume that Q-(0.1, . . . ,n-1) and that 0 is the start state. Recall the algorithm we presented to compute the number of strings of length n from any state j to an accepting state. Let N(j, n) be the number of strings w length n such that (j, u') is in F, i.e., the set of strings of length n that start in state j and reach an accepting state. Clearly, the number of strings of length n accepted by a DFA M are given by N(0,n). The recurrence formula for N(j.n) is given by fG,n)-N(8G, ),n-1). Initial values N (.0) are given by: N (.0) = 1 if j E F, N (j,0) = 0 if jf F. You can iteratively compute N(j, k) for all j for k = 0, 1, , n. As we noted in class, you only need to keep two vectors prev and next of length m. Using the values of N(j,k) stored in prev, you can compute N(j, k +1) for all 0Sjm 1 in nert. Then copy nert to prev and repeat When your main function runs, i will ask for an integer input , and output the number of strings of length n with the specified property. The range of n wl be between1 and 300. The answer should be exact, not a floating-point approximation so you should use a language that supports unlimited precision arithmetic like Java or Python or a library like GMP (in case of C++ Some test cases: Test case 1 Input:n137 Output: 6119266976149912241614898841866546736 Test case 2 Input: n= 100 Output: 987802207638178400131884900 PROBLEM 1: Write a function count that computes the number of strings w of length n over a, b, c with the following property: In any substring of length 4 of w, all three letters a, b and c occur at least once. For example, strings like abbcaabca satisfy the property, but a string like bacaabbcabac does not satisfy the property since the substring aabb does not have a c. The idea is to create a DFA M for the language Lwin any substring of length 4 of w, all three letters a, b and c occur) Suppose M-Q. 6,0,F) states. Assume that Q-(0.1, . . . ,n-1) and that 0 is the start state. Recall the algorithm we presented to compute the number of strings of length n from any state j to an accepting state. Let N(j, n) be the number of strings w length n such that (j, u') is in F, i.e., the set of strings of length n that start in state j and reach an accepting state. Clearly, the number of strings of length n accepted by a DFA M are given by N(0,n). The recurrence formula for N(j.n) is given by fG,n)-N(8G, ),n-1). Initial values N (.0) are given by: N (.0) = 1 if j E F, N (j,0) = 0 if jf F. You can iteratively compute N(j, k) for all j for k = 0, 1, , n. As we noted in class, you only need to keep two vectors prev and next of length m. Using the values of N(j,k) stored in prev, you can compute N(j, k +1) for all 0Sjm 1 in nert. Then copy nert to prev and repeat When your main function runs, i will ask for an integer input , and output the number of strings of length n with the specified property. The range of n wl be between1 and 300. The answer should be exact, not a floating-point approximation so you should use a language that supports unlimited precision arithmetic like Java or Python or a library like GMP (in case of C++ Some test cases: Test case 1 Input:n137 Output: 6119266976149912241614898841866546736 Test case 2 Input: n= 100 Output: 987802207638178400131884900
