Question

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.

Input a DNA sequence: CATTTGCAGGTG

Matching patterns are:

TT
TT
TTT
TTTGCAGGT
TTGCAGGT
TGCAGGT
ATTTGCA

Input a DNA sequence: TTTTAAAA

Matching patterns are:

AAAA AAA AA

TTTT TTT TT

(1) Show a digital copy of the diagram of the DFA.

(2) Show source code C++

Answer 1

#include <bits/stdc++.h>

using namespace std;

int checkEquality(string s)

{

    return (s[0] == s[s.size() - 1]);

}

  

int countSubstringWithEqualEnds(string s)

{

    int result = 0;

    int n = s.length();

  

    // Starting point of substring

    for (int i = 0; i < n; i++)

  

       // Length of substring

       for (int len = 1; len <= n-i; len++)

  

          // Check if current substring has same

          // starting and ending characters.

          if (checkEquality(s.substr(i, len)))

            result++;

  

    return result;

}

  

int main()

{

    string s("abcab");

    cout << countSubstringWithEqualEnds(s);

    return 0;

}