Question

Description:

In this assignment, you will implement a deterministic finite automata (DFA) using C++ programming language to extract all matching patterns (substrings) from a given input DNA sequence string.

1. The alphabet for generating DNA sequences is {A, T, G, C}. Write a regular expression that represents all DNA strings that begin with ‘A’ and end with ‘T’. Note: assume empty string is not a valid string.
2. Design a deterministic finite automaton to recognize the regular expression.
3. 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 (2) to check if all possible substrings in the DNA sequence is a part of the regular expression or not.

Note: even if the same pattern is found multiple times, it should be printed every time it is found. The program should mimic how a DFA processes a string: reading one letter at a time and doing state transitions. Don’t directly check if the string begins with ‘A’ and end with ‘T’.

Below are two sample input/output. Only the bolded are user input.

Input a DNA sequence: CATTTGCAGGTG

Matching patterns are:

AT

ATT

ATTT

ATTTGCAGGT

AGGT

Input a DNA sequence: TTTATAAAA

Matching patterns are:

AT

What to submit:

A zipped file containing the following:

1. A digital copy of the regular expression
2. A digital copy of diagram of the DFA.
3. a cpp file representing your program
4. Screen shots of your output

Answer 1

(a) DFA

q0- initial state

q2- final state

(b) Code

#include <bits/stdc++.h>
using namespace std;

set<string> s2;

void func(string stri)
{
  
   for (int i = 0; i < stri.length(); i++)
   {
       if (stri[i]=='A')
       {
           for (int j = i; j < stri.length(); j++)
           {
               if (stri[j]=='T')
               {
                   string s = stri.substr(i, j);
                   s2.insert(s);
               }
           }
       }
   }
}

int main()
{
   string s = "CATTT";
   func(s);

   for (auto i : s2)
       cout << i << " ";
   cout << endl;

   return 0;
}

Output