Use C++ promming language In this assignment, you will implement a deterministic finite automata (DFA) using C++ programming language to extract matching patterns from a given input DNA sequence string.
1. Design a deterministic finite automata to recognize the regular expression A(A+T+G+C)*A + T(A+T+G+C)*T over the alphaber {A, T,G, C}. This regular expression recognize any string that starts and ends with ‘A’ or starts and ends with ‘T’.
2. Write a program which asks the user to input a DNA sequence. The program should be able to extract all the patterns (substrings present in the DNA sequence) that match the regular expression given in 1. You MUST implement DFA from (1) to check if all possible substrings in the DNA sequence is a part of the regular expression or not. Below are two sample input/output. Only the bolded are user input. Use of external package or library for regular expression matching is not allowed.
example output:
Input a DNA sequence: CATTTGCAGGTG
Matching patterns are:
TT
TT
TTT
TTTGCAGGT
TTGCAGGT
TGCAGGT
ATTTGCA
Input a DNA sequence:
Matching patterns are:

AAA
AA

TTT TT