Question

I would like some assistance correcting an issue I am having with this assignment.

Once a finite state automaton (FSA) is designed, its transition diagram can be translated in a straightforward manner into program code. However, this translation process is considerably tedious if the FSA is large and troublesome if the design is modified. The reason is that the transition information and mechanism are combined in the translation.

To do it differently, we can design a general data structure such as a table or a list to hold the transition information, and to implement in program code only a general transition mechanism. Using this approach, the resulted program is not only smaller, but it can also be modified easily to simulate a different FSA by just changing the transition information and the general data structure holds. We shall refer to such a program as a universal finite state automaton.

Your job for this assignment is to implement such a universal finite state automaton. To convince you that it is very easy to do so, I have suggested an algorithm below; however, you are free to modify it. Note that your program has to be designed to handle the FSA where the input transition function is partial, which means there is a default dead-end, or trap state.

1 state = initial_state; exit = false;

2 while not exit do

3 begin

4 symbol = getNextSymbol();

5 if symbol is in alphabet then begin

6 state = getNextState(state, symbol);

7 if state is dead_end then begin exit = true; reject; end

8 end

9 else begin

10 exit = true;

11 if symbol is not the endmarker then reject;

12 else if state is final then accept;

13 else reject;

14 end //if

15 end //while

The above algorithm shows how to process one input string and correctly determine

whether the string is in the language. You need to augment the algorithm so that your program is able to read in different FSA descriptions from an input file and simulate one machine at a time with any number of test strings.

You must represent each FSA in the input file with the following format, and put all input machines in one file:

(1) The number of states, say N.
For ease of implementation, number states from 0 to N-1, with 0 representing the initial

state, and N the dead-end state.

(2) The set of final states.
You need a boolean array FINAL [0..N-1].

(3) The alphabet.
Symbols in the alphabet should be numbered internally so that the value returned by the

function getNextSymbol is an integer.

(4) A sequence of transitions of the form (p a q).
The triple (p a q) means that in state p, looking at input symbol a, the FSA will change

its state to q. For this project, store this information in a table, say next_state, so that the value returned by the function getNextState is next_state [state, symbol].

Test your program with the following 5 finite state automata using the given test strings.

(1) A FSA which recognizes the set of all binary strings with at most one pair of consecutive 0’s and at most one pair of consecutive 1’s. Strings: , 00, 0011, 110011, 010101, 000, 00102, 1100101, 10110100101, 1001011010110

(2) A FSA which recognizes email addresses. A valid email address is defined as follows: [email protected], where the user name consists of at least one symbol with any combination of letters, digits, hyphens, underscores, or periods. The server name is any string of at least one symbol with any combination of letters, digits, hyphens, and underscores. The domain name must have 2 to 4 letters. Strings: [email protected], jsmith, jsmith@olympus, [email protected], [email protected], jsmith.edu, [email protected], [email protected], [email protected], [email protected]

(3) A FSA which recognizes all identifiers that begin with a letter (both upper and lower), an underscore, or a dollar sign, followed by any combination of letters, digits, underscores, and dollar signs. Strings: a, $, _, TAX_RATE, $amount, week day, 3dGraph, X3y7, _finite_automaton, X*Y

(4) A FSA which recognizes the set of all signed or unsigned decimal numbers without superfluous leading or trailing zeros. For instance, 0.0, -0.5, +120.01, and 123000.0 are in the language, but 0.00, 00.5, and 0123.4 are not. Each decimal number has the form of A.B, where A and B are strings of digits and they cannot be empty at the same time. Strings: +1.23, -.123, 123., -0.0, 01234.5, +789, ., 56.30, +120.0001, 123000.0

(5) A FSA which recognizes the set of strings over {0, 1, 2} such that the final digit has not appeared before. Strings: 0, 01, 012, 22, 2102, 0221, 01012, 120120, 110221210, 0202321

Sample input of a FSA: 2

1
01
(0 0 0) (0 1 1) (1 0 1) (1 1 0) 1000 10001 ........

Corresponding output:
Finite State Automaton #1.

(1) number of states: 2 (2) final states: 1
(3) alphabet: 0, 1
(4) transitions:

000 011 101 110

(5) strings: 1000 accept

10001 reject

........

here is current code, but doesn't seem to be working properly. Some strings that I should be accepting are being rejected

public class Transitions {

public String currentState, nextState, sign;

}

package cs311;

import java.io.*;

import java.util.ArrayList;

public class Automation {

public static ArrayList<Transitions> transitionTable = new ArrayList();

public static String totalStates;

public static int currentPosition = 0;

public static String[] alphabet;

public static String[] finalStates;

//print the FSA number, number states, final states, alphabet, transitions,

//and tested strings

public static void printFSA(int number) {

String result;

System.out.printf("\nFinite State Automaton #%d\n", number);

System.out.printf("(1) Number Of States: %s\n", totalStates);

if (finalStates.length == 0) {

result = "None exist!";

} else {

result = finalStates[0];

for (int i = 1; i < finalStates.length; i++) {

result += ",";

result += finalStates[i];

}

}

System.out.printf("(2) Final States: %s\n", result);

if (alphabet.length == 0) {

result = "None exist!";

} else {

result = alphabet[0];

for (int i = 1; i < alphabet.length; i++) {

result += ",";

result += alphabet[i];

}

}

System.out.printf("(3) Alphabet: %s\n", result);

System.out.println("(4) Transitions:");

transitionTable.stream().forEach((t)

-> {

System.out.printf("\t%s %s %s\n", t.currentState, t.sign, t.nextState);

});

System.out.println("(5) Strings:");

}

//returns the next state given the current state and input symbol

public static String getNextState(String currentState, String sign) {

for (Transitions t : transitionTable) {

if (currentState.equals(t.currentState) && sign.equals(t.sign)) {

return t.nextState;

}

}

return totalStates;

}

//checks if the input symbol is in the alphabet or not

public static boolean isInAlphabet(String symbol) {

for (String alphabet : Automation.alphabet) {

if (symbol.equals(alphabet)) {

return true;

}

}

return false;

}

//returns the following symbol

public static String getNextSymbol(String line) {

return String.valueOf(line.charAt(currentPosition++));

}

//prints whether the current string is accepted or rejected

public static void printResult(String str, String result) {

System.out.printf("%s\t\t%s\n", str, result);

}

public static void main(String[] args) {

final String initial_state = "0";

String state = initial_state, symbol;

String[] tokens;

boolean[] final_states;

int automaton_number = 1;

try (BufferedReader br = new BufferedReader(new FileReader("FSAinput.txt"))) {

String line = "";

do

{

if ((line = br.readLine()) == null)

{

System.exit(0);

}

totalStates = line;

final_states = new boolean[Integer.parseInt(totalStates)];

if ((line = br.readLine()) == null)

{

System.exit(1);

}

finalStates = line.split(" ");

for (String token : finalStates)

{

final_states[Integer.parseInt(token)] = true;

}

if ((line = br.readLine()) == null)

{

System.exit(1);

}

alphabet = line.split(" ");

while ((line = br.readLine()) != null && line.startsWith("("))

{

tokens = line.split(" |\\(|\\)");

for (int i = 3; i < tokens.length; i++)

{

Transitions t = new Transitions();

t.currentState = tokens[1];

t.sign = tokens[2];

t.nextState = tokens[i];

transitionTable.add(t);

}

}

printFSA(automaton_number);

while (line != null && !line.equals("!")) {

while (currentPosition < line.length() || line.length() == 0)

{

if (line.length() != 0) {

symbol = getNextSymbol(line);

} else {

symbol = "";

}

if (isInAlphabet(symbol))

{

state = getNextState(state, symbol);

if (state.equals(totalStates))

{

printResult(line, "REJECT");

break;

}

else if (currentPosition == line.length())

{

if (final_states[Integer.parseInt(state)])

{

printResult(line, "ACCEPT");

break;

} else

{

printResult(line, "REJECT");

break;

}

}

}

else

{

if (currentPosition != line.length())

{

printResult(line, "Reject");

break;

} else if (final_states[Integer.parseInt(state)]

&& (isInAlphabet(symbol) || symbol.isEmpty()))

{

printResult(line, "Accept");

break;

} else

{

printResult(line, "Reject");

break;

}

}

}

currentPosition = 0;

state = initial_state;

line = br.readLine();

}

transitionTable.clear();

automaton_number++;

} while (line != null && line.equals("!"));

} catch (FileNotFoundException e)

{

System.out.println("File not Found!");

} catch (IOException e)

{

   System.out.println(e);

}

}

}

FSAinput.txt

5

0 1 2 3 4

0 1

(0 0 1)

(0 1 3)

(1 0 2)

(1 1 3)

(2 1 3)

(3 0 1)

(3 1 4)

(4 0 1)

00

0011

110011

010101

000

00102

1100101

10110100101

1001011010110

!

Answer 1

Automation.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

public class Automaton {

    static ArrayList<Transition> transition_table = new ArrayList();
    static String num_states;
    static int position = 0;
    static String[] alphabets, final_s;

    public static void main(String[] args) {
   final String initial_state = "0";
   String state = initial_state, symbol;
   String[] tokens;
   boolean[] final_states;
   int automaton_number = 1;

   //TODO: replace "file" with filename
   try (BufferedReader br = new BufferedReader(new FileReader("test.txt"))) {
        String line = "";

        do {
       //begin filling in variables
       if ((line = br.readLine()) == null) {
            System.exit(1);
       }
       num_states = line;

       final_states = new boolean[Integer.parseInt(num_states)];
       if ((line = br.readLine()) == null) {
            System.exit(1);
       }
       final_s = line.split(" ");
       for (String token : final_s) {
            final_states[Integer.parseInt(token)] = true;
       }

       if ((line = br.readLine()) == null) {
            System.exit(1);
       }
       alphabets = line.split(" ");

       //fill in transition table
       while ((line = br.readLine()) != null && line.startsWith("(")) {
            tokens = line.split(" |\\(|\\)");

            for (int i = 3; i < tokens.length; i++) {
           Transition t = new Transition();
           t.state = tokens[1];
           t.symbol = tokens[2];
           t.next_state = tokens[i];

           transition_table.add(t);
            }
       }

       printInfo(automaton_number);

       while (line != null && !line.equals("@")) {
            while (position < line.length() || line.length() == 0) {
           if(line.length() != 0) {
                symbol = getNextSymbol(line);
           } else {
                symbol = "";
           }

           //check if symbol is in the alphabet array
           if (isAlphabet(symbol)) {
                //loop through transition table to get next state if exist; if not,
                //it is dead_end state then reject string and exit
                state = getNextState(state, symbol);

                if (state.equals(num_states)) {
               printResult(line, "REJECT");
               break;
                } else if (position == line.length()) {
               if (final_states[Integer.parseInt(state)]) {
                    printResult(line, "ACCEPT");
                    break;
               } else {
                    printResult(line, "REJECT");
                    break;
               }
                }
           } else {
                if (position != line.length()) {
               printResult(line, "REJECT");
               break;
                } else if (final_states[Integer.parseInt(state)]
                    && (isAlphabet(symbol) || symbol.isEmpty())) {
               printResult(line, "ACCEPT");
               break;
                } else {
               printResult(line, "REJECT");
               break;
                }
           }
            }

            position = 0;
            state = initial_state;
            line = br.readLine();
       }

       transition_table.clear();
       automaton_number++;
        } while (line != null && line.equals("@"));
   } catch (Exception e) {
        System.out.println(e);
   }
    }

    public static class Transition {

   public String state, next_state, symbol;
    }

    //gets current state and given symbol and searches transition table for next state
    public static String getNextState(String state, String symbol) {
   for (Transition t : transition_table) {
        if (state.equals(t.state) && symbol.equals(t.symbol)) {
       //curr state and next st
       return t.next_state;
        }
   }

   //dead_end state returned; state and given symbol not in table
   return num_states;
    }

    public static boolean isAlphabet(String symbol) {
   for (String alphabet : alphabets) {
        if (symbol.equals(alphabet)) {
       return true;
        }
   }

   return false;
    }

    public static String getNextSymbol(String line) {
   return String.valueOf(line.charAt(position++));
    }

    public static void printResult(String line, String result) {
   System.out.printf("%s\t %s\n", line, result);
    }

    public static void printInfo(int auto_num) {
   String out;

   System.out.printf("Finite State Automaton #%d\n", auto_num);
   System.out.printf("1) number of states: %s\n", num_states);

   if (final_s.length == 0) {
        out = "none";
   } else {
        out = final_s[0];
        for (int i = 1; i < final_s.length; i++) {
       out += ", ";
       out += final_s[i];
        }
   }
   System.out.printf("2) final states: %s\n", out);

   if (alphabets.length == 0) {
        out = "none";
   } else {
        out = alphabets[0];
        for (int i = 1; i < alphabets.length; i++) {
       out += ", ";
       out += alphabets[i];
        }
   }
   System.out.printf("3) alphabets: %s\n", out);

   System.out.println("4) transitions:");
   transition_table.stream().forEach((t) -> {
        System.out.printf("\t%s %s %s\n", t.state, t.symbol, t.next_state);
   });

   System.out.println("5) strings:");
    }

}