What to submit:

1. A diagram of the DFA.
2. C++ program
3. Screen shots of your code and output

Description:

In this assignment, you will implement a deterministic finite automaton (DFA) using C++ programming language to test if an input DNA sequence matches a regular expression.

1. The alphabet for generating DNA sequences is {A, T, G, C}. Design a deterministic finite automaton to recognize the regular expression (TT+G)*(A+T). If you can’t design directly the DFA, you can convert the regular expression to NFA and convert the NFA to get DFA.
2. Write a program which asks the user to input a DNA sequence. The program should be able test if the input matches the regular expression given in (1). You MUST implement DFA from (1) to check if the DNA sequence is a part of the regular expression or not.

The program should mimic how a DFA processes a string: reading one letter at a time and doing state transitions. Please see Week 4 materials on DFA implementation in BlackBoard for reference.

Below are four sample input/output. Only the bolded strings are user inputs.

PLEASE MATCH SCREEN OUTPUT:

Input a DNA sequence: GTTTTGT

The pattern GTTTTGT is valid for RE (TT+G)*(A+T)

Input a DNA sequence: GTTTTG

The pattern GTTTTG is not valid for RE (TT+G)*(A+T)

Input a DNA sequence: TTTGT

The pattern TTTGT is not valid for RE (TT+G)*(A+T)

Input a DNA sequence: TTGTTTTA

The pattern TTGTTTTA is valid for RE (TT+G)*(A+T)