I would like some assistance correcting an issue I am having with this assignmen
ID: 3593969 • Letter: I
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: userName@serverName.domainName, 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: a.b.c@d.w3c, jsmith, jsmith@olympus, jsmith@olympus.gov, _jsmith-example.olympus@states.us, jsmith.edu, john@mail.office, ComputerScienceDepartment@csupomona.edu, jsmith@LA.cnn.com, SMITH@bookStore.Peru
(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(" Finite State Automaton #%d ", number);
System.out.printf("(1) Number Of States: %s ", 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 ", 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 ", result);
System.out.println("(4) Transitions:");
transitionTable.stream().forEach((t)
-> {
System.out.printf(" %s %s %s ", 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 %s ", 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
!
Explanation / Answer
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 %s ", line, result);
}
public static void printInfo(int auto_num) {
String out;
System.out.printf("Finite State Automaton #%d ", auto_num);
System.out.printf("1) number of states: %s ", 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 ", 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 ", out);
System.out.println("4) transitions:");
transition_table.stream().forEach((t) -> {
System.out.printf(" %s %s %s ", t.state, t.symbol, t.next_state);
});
System.out.println("5) strings:");
}
}