// F# program to recognize non-context free pattern  C^nA^nT^n
// Version that mutates counters cc and ac

open System;

type state = Start | Cstate | Astate | Tstate | Accept;; // states of the FSM

let mutable si = -1;  // size of pattern found

// global counters
let mutable cc = 0;  // counts number of C's
let mutable ac = 0;  // counts number of A's and T's
let reset(c,a) =  cc <- c;  ac <- a;;

let mutable currentState = Start;  // current state

// given current state, input, action,  **return next state**:
// Since currentState is external, don't need to pass it to fsm:
let fsm input =  
 match (currentState,input) with
  | (Start,'C') ->  cc <- 1;  Cstate
  | (Start,_) -> Start
  | (Cstate,'C') -> cc <- cc+1; Cstate
  | (Cstate,'A') -> ac <- 1; Astate
  | (Astate,'C') -> reset(1,0); Cstate
  | (Astate,'A') when ac<cc -> ac <- ac+1; Astate    
  | (Astate,'T') when ac=1 -> si <- 3;  Accept
  | (Astate,'T') when (ac<=cc && ac>1) -> si <- ac*3; ac <- ac-1; Tstate
  | (Tstate,'T') when ac>1 -> ac <- ac-1; Tstate
  | (Tstate,'T') when ac=1 -> Accept
  | (Tstate,'C') -> reset(1,0); Cstate
  | (Accept,_) -> Accept
  | _ -> reset(0,0); Start


Console.Write("Enter DNA sequence: ");
let input = Console.ReadLine()
let mutable i = 0;    // index for instring
while currentState<>Accept && i < input.Length do
    printf "current state: %s" (string currentState)
    printfn ", input: %c" input[i]
    currentState <- fsm(input[i]);
    i <- i+1;

// report result
match currentState with
 | Accept -> 
    printf "Pattern found starting at position %d, size %d\n" (i - si) (si)
 | _ -> 
    printf "Pattern not found\n";;