DFA text code file

1001001000000111110110110011111

Consider the regular expression 0(0+1)*0 1(0+1)*1 over the alphabet 10,1). This regular expression describes strings that begins and ends with the same character A DFA that recognizes this regular expression is given below. Your task is to write a C++ program to implement the given DFA. Your program should also be able to read a long string (consisting of O's and 1's) contained in a text file. The program must use the DFA implementation to find and print out every substring (of length between 3 and 5) in the text file with their locations which are recognized by the DFA. Note that the same substring may occur more than once in the string Let's say it occurs twice. If it is accepted by the DFA, it should be printed twice. A test file is provided for you on BlackBoard For example, if the text file contains the string 00010011. The valid substrings (of length between 3 and 5) recognized by the DFA are 000 at position 1 010 at position 3 0010 at position 2 0010 at position 2 0100 at position 3 1001 at position 4 0 0 1 Q2 Q4 1 Q1 1 0 0 00010 at position 1 Q5 0 00100 at position 2 1 10011 at position 4 Note: To find valid substrings, you can't simply check if the substring begins and ends with the same character. The substring must be 'fed' to your DFA implementation. If it ends up in one of the final state, it is valid, otherwise not valid Consider the regular expression 0(0+1)*0 1(0+1)*1 over the alphabet 10,1). This regular expression describes strings that begins and ends with the same character A DFA that recognizes this regular expression is given below. Your task is to write a C++ program to implement the given DFA. Your program should also be able to read a long string (consisting of O's and 1's) contained in a text file. The program must use the DFA implementation to find and print out every substring (of length between 3 and 5) in the text file with their locations which are recognized by the DFA. Note that the same substring may occur more than once in the string Let's say it occurs twice. If it is accepted by the DFA, it should be printed twice. A test file is provided for you on BlackBoard For example, if the text file contains the string 00010011. The valid substrings (of length between 3 and 5) recognized by the DFA are 000 at position 1 010 at position 3 0010 at position 2 0010 at position 2 0100 at position 3 1001 at position 4 0 0 1 Q2 Q4 1 Q1 1 0 0 00010 at position 1 Q5 0 00100 at position 2 1 10011 at position 4 Note: To find valid substrings, you can't simply check if the substring begins and ends with the same character. The substring must be 'fed' to your DFA implementation. If it ends up in one of the final state, it is valid, otherwise not valid