private static String[][] HFSA(String[] input) {
        int NGramLength = input.length;
        //String[] transitions = {" ", ",COMMA", ".PERIOD", "?QMARK", "!EXCL"}; //Change space to null
        int numberOfTransitionsInString = input.length/2;
        int internalCounters[] = new int[numberOfTransitionsInString];
        Arrays.fill(internalCounters, transitions.length-1);
        int numberOfReturnValues = (int)Math.pow(transitions.length, numberOfTransitionsInString);
        String[][] returnValue = new String[numberOfReturnValues][NGramLength];

        int counter = 0;
        while (internalCounters[0]>=0) {
            int positionInInnerArray = 0;
            int positionInOuterArray = 0;
            String[] string = new String[input.length];

            for(int i = 0; i < numberOfTransitionsInString; i++) {
                string[positionInInnerArray] = input[positionInOuterArray];
                positionInOuterArray++;
                positionInInnerArray++;
                if(!transitions[internalCounters[i]].equals(" ")) {
                    string[positionInInnerArray] = transitions[internalCounters[i]];
                    positionInInnerArray++;
                } else {
                    string[positionInInnerArray] = input[positionInOuterArray];
                    positionInInnerArray++;
                    positionInOuterArray++;
                }
            }
            for(int i = positionInInnerArray; i < NGramLength; i++) {
                string[i] = input[positionInOuterArray];
                positionInOuterArray++;
            }

            internalCounters[internalCounters.length-1]--;

            for(int i = internalCounters.length-1; i > 0; i--) {
                if(internalCounters[i]<0) {
                    internalCounters[i] = transitions.length-1;
                    internalCounters[i-1]--;
                }
            }

            returnValue[counter] = string;
            counter++;
        }

        return returnValue;
    }