Assignment 3: 4th question. Chapter 5 - Finite automata T. Sudkamp text: Read Ch
ID: 3679989 • Letter: A
Question
Assignment 3: 4th question. Chapter 5 - Finite automata
T. Sudkamp text: Read Ch. 5.
Programming assignment: Construct a DFA simulator. The program should be general, i.e., it needs to work for any DFA, just by reading in the transition table and other needed information. The output should include the computation (i.e., the sequence of configurations) on the input of the DFA and string, ended by 'ACCEPT' or 'REJECT'.
Run for the assigned DFAs in the text, 5.2.2 p. 150, 5.3.1 p. 153, 5.3.3 p. 154 and 5.3.6 p. 156 [ pdf ]. Show the input and output for a string that should be accepted and a string that should be rejected. Also submit a listing of your well-documented program, a screenshot or job log showing compilation and execution, and your input and output files.
link for reference : https://cs.wmich.edu/elise/courses/cs480/HW3-examples-S16.pdf
Explanation / Answer
Program:
import java.io.*;
import java.util.*;
public class Dfasimulator{
public int[][] Transition=new int[20][20];
public int alphaset,stateset;
public ArrayList<Character> alphabet;
public Set<Integer> finalstates;
public void builtdfa() throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("please enter the no. of alphabets in the alphabet set of DFA");
alphaset=Integer.parseInt(br.readLine());
//System.out.println(alphaset);
System.out.println("please enter the no. of states in the set of DFA");
stateset=Integer.parseInt(br.readLine());
System.out.println("please enter all the alphabets of the DFA simultaneosly");
String alphabets=br.readLine();
alphabet=new ArrayList<Character>();
for(int i=0;i<alphabets.length();i++){
alphabet.add(alphabets.charAt(i));
}
//System.out.println(alphabet);
for(int s=0;s<stateset;s++)
{
System.out.println("enter the row entries of the transition table");
for(int r=0;r<alphaset;r++)
{int int1=Integer.parseInt(br.readLine());
Transition[s][r]=int1;
}
}
finalstates=new HashSet<Integer>();
System.out.println("please enter the final states of the DFA ");
System.out.println("when you are done of giving the inputs enter -2 to stop feeding final states");
int int2=Integer.parseInt(br.readLine());
while(int2!=-2)
{ finalstates.add(int2);
int2=Integer.parseInt(br.readLine());
}
System.out.println(finalstates);
DfaTest();
}
public void DfaTest()throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int state;
System.out.println("enter the starting state");
state=Integer.parseInt(br.readLine());
System.out.println("give input to the DFA ");
System.out.println("end your input with # character ");
String input=br.readLine();
int index=0;
while(input.charAt(index)!='#')
{
char char1=input.charAt(index);
int index1=alphabet.indexOf(char1);
state=Transition[state][index1];
index++;
}
System.out.println(" final state after giving the input is "+state);
if (finalstates.contains(state))
System.out.print("your input string is accepted by the DFA");
else
System.out.println("the input string is rejected by the DFA");
}
public static void main(String args[])throws Exception{
Dfasimulator raw=new Dfasimulator();
raw.builtdfa();
//System.out.println(raw.alphaset);
}
}
output 1:
please enter the no. of alphabets in the alphabet set of DFA
2
please enter the no. of states in the set of DFA
3
please enter all the alphabets of the DFA simultaneosly
a b
enter the row entries of the transition table
0
1
enter the row entries of the transition table
0
3
enter the row entries of the transition table
2
2
please enter the final states of the DFA
when you are done of giving the inputs enter -2 to stop feeding final states
2
-2
[2]
enter the starting state
0
give input to the DFA
end your input with # character
abba
your input string is accepted by the DFA.
ouput2:
please enter the no. of alphabets in the alphabet set of DFA
3
please enter the no. of states in the set of DFA
7
please enter all the alphabets of the DFA simultaneosly
n d q
enter the row entries of the transition table
0
0
0
enter the row entries of the transition table
0
0
0
enter the row entries of the transition table
1
0
0
enter the row entries of the transition table
2
1
0
enter the row entries of the transition table
3
2
0
enter the row entries of the transition table
4
3
0
enter the row entries of the transition table
1
4
1
please enter the final states of the DFA
when you are done of giving the inputs enter -2 to stop feeding final states
2
-2
[2]
enter the starting state
0
give input to the DFA
end your input with # character
abba
your input string is accepted by the DFA.