-
Notifications
You must be signed in to change notification settings - Fork 0
/
nfatodfa.java~
111 lines (110 loc) · 3.18 KB
/
nfatodfa.java~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import java.io.*;
import java.util.*;
public class nfatodfa
{
public static int states,inputs;
public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int l,p,q,ctr=0;
String start,end,a="",b="",t,c="";
Set<String> set = new HashSet<String>();
System.out.print("Number of states:- ");
states=Integer.parseInt(br.readLine());
System.out.print("Number of inputs:- ");
inputs=Integer.parseInt(br.readLine());
System.out.print("Start State:- ");
start=br.readLine();
System.out.print("End State:- ");
end=br.readLine().replace("{","").replace("}","");
List<String> endlist = new ArrayList<String>(Arrays.asList(end.split(" , ")));
String arr[][]=new String[(int)Math.pow(2,states)][inputs];
for(ctr=0;ctr<states;ctr++)
{
for(int j=0;j<inputs;j++)
{
System.out.print("State "+(char)(ctr+112)+" Input "+(j)+" :- ");
arr[ctr][j]=br.readLine();
}
}
for(int i=0;i<states;i++) //develop power set
a=a+"0";
for(int j=0;j<states-1;j++)
b=b+"0";
b=b+"1";
set.add("{0}");
p=Integer.parseInt(a,2);
q=Integer.parseInt(b,2);
for(int z=0;z<=Math.pow(2,states)-2;z++)
{
p=p+q;
t=Integer.toBinaryString(p);
l=states-t.length();
for(int y=0;y<l;y++)
t="0"+t;
for(int x=0;x<t.length();x++)
if (t.charAt(x)=='1')
c=c+","+(char)(x+112);
if(c.length()!=2) // removing states already present in transition table
set.add("{"+c.substring(1,c.length())+"}");
c="";
}
Iterator iter=set.iterator();
while(iter.hasNext())
{
String temp=iter.next().toString().replace("{","").replace("}","").replace(",","");
if(temp.equals("0"))
{
arr[ctr][0]="{0}";
arr[ctr][1]="{0}";
ctr=ctr+1;
}
else
{
char temparr[]=temp.toCharArray();
for(int o=0;o<inputs;o++)
{
SortedSet<String> tempset = new TreeSet<String>(Arrays.asList(arr[(int)temparr[0]-112][o].replace("{","").replace("}","").split(",")));
for(int m=0;m<temparr.length;m++)
tempset.addAll(Arrays.asList(arr[(int)temparr[m]-112][o].replace("{","").replace("}","").split(",")));
if(tempset.contains("0"))
tempset.remove("0");
if(tempset.isEmpty())
tempset.add("0");
arr[ctr][o]=tempset.toString().replace("[","{").replace("]","}").replace(" ","");
}
ctr=ctr+1;
}
}
List<String> list = new ArrayList<String>(set);
for(int i=0;i<states;i++)
list.add(i,"{"+(char)(i+112)+"}");
String[] str=list.toArray(new String[list.size()]);
List<Integer> indexset=new ArrayList<Integer>();
indexset.add(list.indexOf(start));
ListIterator it=indexset.listIterator();
while(it.hasNext())
{
int pos=(int)it.next();
for(int u=0;u<inputs;u++)
if(!indexset.contains(list.indexOf(arr[pos][u])))
{
it.add(list.indexOf(arr[pos][u]));
it.previous();
}
}
System.out.println("\nReduced Transition Table");
for(int i=0;i<inputs;i++)
System.out.print("\t"+i);
System.out.println();
for(int v=0;v<indexset.size();v++)
{
System.out.print(str[indexset.get(v)]+"\t");
for(int w=0;w<inputs;w++)
{
System.out.print(arr[indexset.get(v)][w]+"\t");
}
System.out.println();
}
}
}