(Errors with my code) Assignment: Purpose: To model a DFA (Deterministic Finite
ID: 3711608 • Letter: #
Question
(Errors with my code)
Assignment:
Purpose: To model a DFA (Deterministic Finite Automaton) and use it to accept strings
of the associated language.
Input: The program should take the DFA description from a text file that is specified as a
command line parameter. If this parameter is missing, the user should be prompted for
the data file. Strings to be tested for inclusion in the language should be entered
interactively by the user.
Output: For each string being tested, the program should indicate whether or not the
string is accepted.
DFA input format:
line 1: alphabet - eg. {0,1}
line 2: states - eg. {a,b,c,d,e}
line 3: start state - eg. a
line 4: accept states - eg. {d,e}
lines 5-: transition fn - eg. (a,0)->b
(a,1)->c
etc.
Notes:
• Assume no spaces in input.
• Alphabet must at least allow {0,1}. Please feel free to expand this.
• States must at least allow lower case letters, but you are welcome to expand this
to numerals and upper case letters.
• Transition functions may appear in any order in the input text file. End of the
input file indicates the end of transition functions.
• Name the source code file Dfa.java.
• You are encouraged to team up with other students in class for the project with no
more than 5 students per team. Full participation of each member in a team is
expected.
When your team has finished the project, you will upload (submit) it to the “Project”
dropbox folder in folio. I remind you that if you do not submit the project before the due
date, you will not be able to submit it.
1. Complete the assignment including the following contents: 1) the source code
file, 2) a sample DFA text file, 3) screenshots of your result, 4) a README file to
discuss the details of your program.
2. Return to the dropbox folder for this project.
Spring 2018 Instructor: Dr. Lixin Li
3. Look for the “Add a File” button in the Submit Files area.
4. Browse for the project files that you have on your computer, and select them so
that they upload to the assignment area.
5. Each group only need to submit one set of files.
6. Click “Submit”.
DFA-Test.txt
{0,1}
{a,b,c,d}
a
{d}
(a,0)->b
(a,1)->a
(b,0)->c
(b,1)->a
(c,0)->c
(c,1)->d
(d,0)->d
(d,1)->d
DFA.Java
package Theory2;
import java.awt.Component;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import javax.swing.JOptionPane;
public class DFA {
private static Set<Integer> alphabet = new HashSet<Integer>();
private static Set<CurrentState> states = new HashSet<CurrentState>();
private static CurrentState startingState;
private static Set<Transition> transitionFunction = new HashSet<Transition>();
public static void main(String[] args) {
String fileName, input = null;
if (args.length != 0) {
fileName = args[0];
}
else {
Component frame = null;
fileName = JOptionPane.showInputDialog(
frame,
"Gimme dat juicy file name with the fat extension and full motha flippin path ",
"Requested File",
JOptionPane.PLAIN_MESSAGE);
}
File file = new File(fileName);
try {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
String line = null;
// Read first line of alphabet
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] alphabet = line.split(",");
// Add alphabet to set
for (String s: alphabet) {
addToAlphabet(Integer.parseInt(s));;
}
// Read second line of states
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] stateNames = line.split(",");
// Add states to set
for (String s: stateNames) {
CurrentState state = new CurrentState(s.charAt(0));
state.setAcceptState(true);
addToStates(state);
}
// Read third line of start state
line = br.readLine();
startingState = getStatebyName(line.charAt(0));
// Read fourth line of accept states
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] acceptStateLetters = line.split(",");
// Set those states to final states also
for (String s: acceptStateLetters) {
char name = s.charAt(0);
states.stream().filter(state -> state.getName() == name).forEach(state -> makeFinalState(state));
}
//Read fifth line of transition functions
line = br.readLine();
String pattern = "\((\w),(\w)\)(\W*)(\w)";
Pattern r = Pattern.compile(pattern);
Matcher m = r.matcher(line);
while (m.find()) {
Transition transition = new Transition(getStatebyName(m.group(1).charAt(0)), Integer.parseInt(m.group(2)), getStatebyName(m.group(4).charAt(0)));
addTransition(transition);
}
br.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
while (true) {
Component frame = null;
input = JOptionPane.showInputDialog(
frame ,
"Enter string of ints to test the consutrcted DFA NO NULLS ALLOWED!",
"Test the DFA",
JOptionPane.PLAIN_MESSAGE);
if (input == "exit"){
System.exit(0);
break;
}
else {
String[] inputArray = input.split("");
LinkedList<Integer> inputList = new LinkedList<>(); //Linked lists are dangerous
for (String s: inputArray) {
if (!isInteger(s)) {
JOptionPane.showMessageDialog(frame, input + " Rejected for not being a number between 0 and 1");
break;
}
inputList.add(Integer.parseInt(s));
}
if (calculateFinalState(startingState, inputList)) {
JOptionPane.showMessageDialog(frame, " Accepted in what world? Bro you have no friends...");
continue;
}
else {
JOptionPane.showMessageDialog(frame, input + " Rejected... Just like all the women you asked out");
continue;
}
}
}
}
private static boolean isInteger(String s) {
char c = s.charAt(0);
return (c >= 48 && c <= 57);
}
private static void makeFinalState(CurrentState state) {
state.setFinalState(true);
}
private static CurrentState getStatebyName(char name) {
return states.stream().filter(s -> s.getName() == name).findFirst().get();
}
public static void addToAlphabet(Integer letter) {
alphabet.add(letter);
}
public static void removeFromAlphabet(Integer letter){
alphabet.remove(letter);
}
public static void addToStates(CurrentState state){
states.add(state);
}
public static void removeToState(CurrentState state){
states.remove(state);
}
public static void removeTransition(Transition transition){
transitionFunction.remove(transition);
}
public static void addTransition(Transition transition) throws IllegalArgumentException{
// no 2 outputs for same input+letter
if(transitionFunction.stream().noneMatch(t -> t.getInputState().equals(transition.getInputState()) && t.getSymbol() == transition.getSymbol())){
transitionFunction.add(transition);
} else {
throw new IllegalArgumentException();
}
}
public Set<CurrentState> getAcceptStates(){
return states.stream().filter(s -> s.isAcceptState()).collect(Collectors.toSet());
}
public static boolean calculateFinalState(CurrentState state, Queue<Integer> letter) {
if(letter.isEmpty() && state.isFinalState()){
return true;
}
if(!alphabet.contains(letter.peek())){
return false;
}
Optional<CurrentState> nextState = getNextState(state, letter.poll());
if(nextState.isPresent()){
return calculateFinalState(nextState.get(), letter);
}
return false;
}
private static Optional<CurrentState> getNextState(CurrentState state, Integer alphabet){
return transitionFunction.stream().filter(t -> t.getInputState().equals(state) && t.getSymbol() == alphabet).map(t -> t.getOutputState()).findFirst();
}
}
CurrentState.java
package Theory2;
public class CurrentState {
private boolean finalState = false;
private boolean acceptState = false;
private char name;
//not gonna lie most of this code was generated thanks Eclipse!
public CurrentState(char name) {
this.name = name;
}
public char getName() {
return name;
}
public void setName(char name) {
this.name = name;
}
public boolean isFinalState() {
return finalState;
}
public void setFinalState(boolean finalState) {
this.finalState = finalState;
}
public boolean isAcceptState() {
return acceptState;
}
public void setAcceptState(boolean acceptState) {
this.acceptState = acceptState;
}
}
Transition.java
package Theory2;
public class Transition {
CurrentState input;
Integer symbol;
CurrentState output;
//not gonna lie most of this code was generated too thanks Eclipse!
public Transition(CurrentState input, Integer symbol, CurrentState output){
this.input = input;
this.symbol = symbol;
this.output = output;
}
public CurrentState getInputState() {
return input;
}
public Integer getSymbol() {
return symbol;
}
public CurrentState getOutputState() {
return output;
}
}
Explanation / Answer
ANS:-
PROGRAM:-
STATE CLASS
public class State {
private boolean finalState = false;
private boolean acceptState = false;
private char name;
public State(char name) {
this.name = name;
}
public char getName() {
return name;
}
public void setName(char name) {
this.name = name;
}
public boolean isFinalState() {
return finalState;
}
public void setFinalState(boolean finalState) {
this.finalState = finalState;
}
public boolean isAcceptState() {
return acceptState;
}
public void setAcceptState(boolean acceptState) {
this.acceptState = acceptState;
}
}
Transition Class
public class Transition {
State input;
Integer symbol;
State output;
public Transition(State input, Integer symbol, State output){
this.input = input;
this.symbol = symbol;
this.output = output;
}
public State getInputState() {
return input;
}
public Integer getSymbol() {
return symbol;
}
public State getOutputState() {
return output;
}
}
Dfa class
package chegg;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Optional;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
public class Dfa {
private static Set<Integer> alphabet = new HashSet<Integer>();
private static Set<State> states = new HashSet<State>();
private static State startState;
private static Set<Transition> transitionFunction = new HashSet<Transition>();
public static void main(String[] args) {
String fileName, input = null;
if (args.length != 0) {
fileName = args[0];
}
else {
System.out.println("Please enter file name of data file");
Scanner scanner = new Scanner(System.in);
fileName = scanner.nextLine();
}
File file = new File(fileName);
try {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
String line = null;
// Read first line of alphabets
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] alphabets = line.split(",");
// Add alphabets to set
for (String s: alphabets) {
addToAlphabet(Integer.parseInt(s));;
}
// Read second line of states
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] stateNames = line.split(",");
// Add states to set
for (String s: stateNames) {
State state = new State(s.charAt(0));
state.setAcceptState(true);
addToStates(state);
}
// Read third line of start state
line = br.readLine();
startState = getStatebyName(line.charAt(0));
// Read fourth line of accept states
line = br.readLine();
line = line.substring(1, line.length()-1);
String[] acceptStateNames = line.split(",");
// Set those states to final states also
for (String s: acceptStateNames) {
char name = s.charAt(0);
states.stream()
.filter(state -> state.getName() == name)
.forEach(state -> makeFinalState(state));
}
//Read fifth line of transition functions
line = br.readLine();
String pattern = "\((\w),(\w)\)(\W*)(\w)";
Pattern r = Pattern.compile(pattern);
Matcher m = r.matcher(line);
while (m.find()) {
Transition transition = new Transition(getStatebyName(m.group(1).charAt(0)), Integer.parseInt(m.group(2)), getStatebyName(m.group(4).charAt(0)));
addTransition(transition);
}
br.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("Enter string to test or exit to stop the program");
input = scanner.nextLine();
if (input == "exit")
break;
else {
String[] inputArray = input.split("");
LinkedList<Integer> inputList = new LinkedList<>();
for (String s: inputArray) {
if (!isInteger(s)) {
System.out.println("Rejected");
break;
}
inputList.add(Integer.parseInt(s));
}
if (calculateFinalState(startState, inputList)) {
System.out.println("Accepted");
continue;
}
else {
System.out.println("Rejected");
continue;
}
}
}
}
private static boolean isInteger(String s) {
char c = s.charAt(0);
return (c >= 48 && c <= 57);
}
private static void makeFinalState(State state) {
state.setFinalState(true);
}
private static State getStatebyName(char name) {
return states.stream()
.filter(s -> s.getName() == name)
.findFirst()
.get();
}
public static void addToAlphabet(Integer symbol) {
alphabet.add(symbol);
}
public static void removeFromAlphabet(Integer symbol){
alphabet.remove(symbol);
}
public static void addToStates(State state){
states.add(state);
}
public static void removeToState(State state){
states.remove(state);
}
public static void removeTransition(Transition transition){
transitionFunction.remove(transition);
}
public static void addTransition(Transition transition) throws IllegalArgumentException{
// no 2 outputs for same input+symbol
if(transitionFunction.stream()
.noneMatch(t -> t.getInputState().equals(transition.getInputState()) &&
t.getSymbol() == transition.getSymbol())){
transitionFunction.add(transition);
} else {
throw new IllegalArgumentException();
}
}
public Set<State> getAcceptStates(){
return states.stream().filter(s -> s.isAcceptState())
.collect(Collectors.toSet());
}
public static boolean calculateFinalState(State state, Queue<Integer> symbol) {
if(symbol.isEmpty() && state.isFinalState()){
return true;
}
if(!alphabet.contains(symbol.peek())){
return false;
}
Optional<State> nextState = getNextState(state, symbol.poll());
if(nextState.isPresent()){
return
calculateFinalState(nextState.get(), symbol);
}
return false;
}
private static Optional<State> getNextState(State state, Integer alphabet){
return
transitionFunction.stream()
.filter(t -> t.getInputState().equals(state) &&
t.getSymbol() == alphabet)
.map(t -> t.getOutputState()).findFirst();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.