Thread: Not sure how to work with multiple delimiters. Also, there is random tabbing.

The instructor sometimes has tabs in the input files at random places. To make things more annoying, it's on a UNIX thing which means I have to go get it from the Exceed on Demand 8 and somehow mail it to myself and then download it. Merely copying it might lose some of the formatting perhaps.

Not quite sure. There was sometimes tabs that looked like spaces in there. That's why I had to tell it not to read in that second line if it was blank. It was coming across tabs and possibly a newline. Or something.

The first line is the number of states.

The next line, or what should have been the next line, should contain the alphabet. Again, I thought that using a toCharArray and filtering out the tab and space characters was the best idea.

After that, it starts with a state number and then a bunch of input sets. It's a finite state machine. I want to say it's a Nondeterministic finite state machine. I'm to convert it to a deterministic finite state machine. However, I am trying to figure out how to filter out multiple unwanted characters like , { } and :

Also, another thing I'd been wondering is, since Strings are immutable, i.e. not changeable, then how do setter methods with type String work then?

How do you work with multiple delimiters?

I want it to read in the number to the left of the ":" as a state, starting at 0. (They all do, though in theory they could start at some other state. The starting state is the second to last line in the file.

I think the one to the left of the ":" was the first index for the 2D Array of the MySet class (which is basically an ArrayList).

The stuff on the right are the sets of next states.

See this page for more of an idea, I can't explain it that well. frame set of ITK 328, Spring 2008, Illinois State University, Introduction to the theory of computation

The states are denoted by the { } and the individual values are separated by a ,. An empty state will simply not be added to the ArrayList.

The character alphabet I think is going to have all the values there, plus one for an empty string. I'm using the index of each character, or where it's at in the ArrayList of Character as the second index in the 2D Array

For instance, assuming I have MySet[][] ms, then

a b
0: {1} {} {1,2}

Would have

ms[0][0].add(1);
don't add any for
ms[0][1] since it's empty
For the empty string, which I guess is index 2
ms[0][2].add(1);
ms[0][2].add(2);

What I guess I'm after is:

String str = reader.nextLine(); // assuming it's not empty or something, which was the case I've found already once before

Ok, I'm not even sure how to pseudocode this, hence why I'm here. Here it goes though

1.) Read in each line, perhaps as a whole entity
2.) Go through and scan till it reaches a ":", or the scanner has reader end of file, need to check for that too possibly
3.) Then scan from every { it finds and stop pushing into that part of the ArrayList when it meets a } and then go into the next ArrayList and push the same way and so on until all the alphabet plus the empty string part of it are all done. There is nothing there in between the { and } then don't push. Also, there might be like

{1,2,3,4} so I need to push each number but not the commas
4.) Read in starting state (Easy, assuming I can know that I'm done with the top part as its size will vary. Since the first line in the whole document is the number of states, that should make it easy to find where to read in the starting state.
5.) Read in the final state which could be empty, though it probably isn't, or could have 1 or more parts, again with { } and some commas in between.

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
 
 
public class fsm
{
 
private static class FileParser
{
 
 
 
}
 
private static class MySet
{
 
private  ArrayList<Integer> intList;
 
 
public  void add(Integer data)
{
intList.add(data);
 
}
 
public void remove()
{
intList.remove(0);
 
}
 
 
 
 
 
 
}
 
    public static void main(String[] args)
    {
	Scanner s = null;
	Scanner s2 = null;
	ArrayList<Integer> stateList = new ArrayList<Integer>();
	ArrayList<Character> alphabet = new ArrayList<Character>();
 
 
 
 
 
	int numOfStates = 0;
 
try
    {
   s  = new Scanner(new File(args[0]));
    }
 
    catch (ArrayIndexOutOfBoundsException aioobe)
    {
    System.out.println("Error!");
    System.exit(1);
 
    }
 
catch (FileNotFoundException fnfe)
    {
	System.out.println("Error!");
	System.exit(1);
 
    }
numOfStates = s.nextInt();
 
    System.out.println(numOfStates);
 
    String line = s.nextLine();
    if (line.equals(""))
    line = s.nextLine();
 
 
 
 
    System.out.println(line);
 
    char[] chars = line.toCharArray();
 
 
 
 
    char empty = ' ';
 
 
    String tab = "\t";
    char tab2 = tab.charAt(0);
 
    for (int i =0; i < chars.length; i++)
    {
    if (chars[i]!= empty && chars[i]!=tab2)
    {
    alphabet.add(chars[i]);
    }
    }
 
    alphabet.add('¸');
 
     System.out.println(alphabet.toString());
try
    {
   s2  = new Scanner(new File(args[1]));
    }
 
    catch (ArrayIndexOutOfBoundsException aioobe)
    {
    System.out.println("Error!");
    System.exit(1);
 
    }
 
catch (FileNotFoundException fnfe)
    {
	System.out.println("Error!");
	System.exit(1);
 
    }
 
 
 
 
 
    }
 
}

As I'm trying to figure out how to get all the delimiters for the same line, I'm not even sure how to start.

[nfa2.nfa]
6
a b
0: {1} {4} {2}
1: {5} {2} {}
2: {5} {} {}
3: {} {} {0}
4: {} {1} {3}
5: {} {} {4}
0
{5}
[/nfa2.nfa]

That one didn't have commas and multiple states but this one does:

[nfa4.nfa]
5
a b c d
0: {} {} {} {} {1,2,3,4}
1: {} {1} {1} {1} {}
2: {2} {} {2} {2} {}
3: {3} {3} {} {3} {}
4: {4} {4} {4} {} {}
0
{1,2,3,4}
[/nfa4.nfa]

There's a bunch of text files and it should be able to work on them all.

Once I can get this part, I'll try and see how to convert to a DFSM.

----Edit-----
Ok, that didn't go directly to the program page. However, it's the one program mentioned there. It says 2008 on the line I posted above but it's for 2012.

I've tried to figure out how to do multiple regex but am not sure how yet.

I tried the split method in String, but that would go wrong if it came across

{1,2,3,4}, {1}

though it would work with

{1},{2},{}

I'm trying to split it up around 4 different regex, one a sort of pair

I want it to first split it to everything before it first encounters a ":" and everything after it first encounters a ":"

The split method should be able to handle that, provided I don't have any more blank lines hidden, however, the , and the { } are still confusing me.

I can't have it split around each {} as that's an illegal regex it said. If I could, then I'd have it split it yet again after that around commas.

It would make a ton of smaller arrays but would get what I wanted done. But how to split it around { } if there's something in the middle, or even if there isn't for that matter? I don't want it splitting around only { or only } but around to check when it sees a { and then later when it sees a } to split after the }

I can't just split around the } as I'd pick up the { as a token which I don't want to do.

Also, I'd like to get it to know when it's removing a :, {} , or , as I'd need it to know where to insert it in the 2D array. Only the numbers will be inserted. If I could get the split to do what I'd wanted, I'd probably be able to use the indexes of each of these sub arrays to do that.

I was able to solve that part. However, now I kind of need help with a recursive part.

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
 
 
 
public class fsm
{
 
private static class FileParser
{
 
 
 
}
 
private static class MySet
{
 
private  ArrayList<Integer> intList;
 
public MySet()
{
intList = new ArrayList<Integer>();
 
}
 
public  void add(Integer data)
{
intList.add(data);
 
}
 
public void remove()
{
intList.remove(0);
 
}
 
public int size()
{
return intList.size();
}
 
public Integer get(int index) throws NullPointerException
{
return intList.get(index);
 
}
 
 
 
 
}
 
    public static void main(String[] args)
    {
	Scanner s = null;
	Scanner s2 = null;
	ArrayList<Integer> stateList = new ArrayList<Integer>();
	ArrayList<Character> alphabet = new ArrayList<Character>();
 
	ArrayList<String> transitionLines = new ArrayList<String>();
	ArrayList<String[]> splitArray = new ArrayList<String[]>();
 
 
 
 
 
 
 
 
	int numOfStates = 0;
 
try
    {
   s  = new Scanner(new File(args[0]));
    }
 
    catch (ArrayIndexOutOfBoundsException aioobe)
    {
    System.out.println("Error!");
    System.exit(1);
 
    }
 
catch (FileNotFoundException fnfe)
    {
	System.out.println("Error!");
	System.exit(1);
 
    }
numOfStates = s.nextInt();
 
    System.out.println(numOfStates);
 
    String[][] splits = new String[numOfStates][2];
 
 
 
 
    String line = s.nextLine();
    if (line.equals(""))
    line = s.nextLine();
 
 
 
 
    System.out.println(line);
 
    char[] chars = line.toCharArray();
 
 
 
 
    char empty = ' ';
 
 
    String tab = "\t";
    char tab2 = tab.charAt(0);
 
    for (int i =0; i < chars.length; i++)
    {
    if (chars[i]!= empty && chars[i]!=tab2)
    {
    alphabet.add(chars[i]);
    }
    }
 
    alphabet.add('¸');
 
     System.out.println(alphabet.toString());
 
 
     for (int i=0; i < numOfStates; i++)
     {
     transitionLines.add(s.nextLine());
 
     }
 
     System.out.println(transitionLines.toString());
 
 
     for (int i =0; i < splits.length; i++)
     {
     splits[i] = transitionLines.get(i).split(":");
 
     }
 
 
     for (int i =0; i < splits.length; i++)
     {
     for (int j=0; j < splits[i].length; j++)
     {
     System.out.println(splits[i][j]);
 
     }
 
 
     }
 
   //  String[][] test = 
     ArrayList<String[]> fredBowling = new ArrayList<String[]>();
 
     for (int i =0; i < splits.length; i++)
     {
     fredBowling.add(splits[i][1].split("}"));
     }
     splits[0][1].split("}");
 
     ArrayList<Integer> state = new ArrayList<Integer>();
 
     for (int i=0; i < splits.length; i++)
     {
     state.add(Integer.parseInt(splits[i][0]));
 
     }
 
 
   //  System.out.println(java.util.Arrays.toString(test));
 
 
    // String smaller[] = new String[test.length];
 
    ArrayList<ArrayList<String>> smaller = new ArrayList<ArrayList<String>>();
 
     for (int i =0; i < fredBowling.size(); i++)
     {
     smaller.add(new ArrayList<String>());
     for (int j = 0; j < fredBowling.get(i).length; j++)
     {
     int temp = fredBowling.get(i)[j].indexOf("{");
 
     smaller.get(i).add(fredBowling.get(i)[j].substring(temp + 1));
     }
 
     }
 
   //  System.out.println(java.util.Arrays.toString(smaller));
 
    //  ArrayList<String[]> finale = new ArrayList<String[]>();
     ArrayList<ArrayList<String[]>> finale = new ArrayList<ArrayList<String[]>>();
 
     // for (int i =0; i < smaller.length; i++)
  //    {
   //   finale.add(smaller[i].split(","));
 
 //    }
 
     for (int i =0; i < smaller.size(); i++)
     {
     finale.add(new ArrayList<String[]>());
     for (int j =0; j < smaller.get(i).size(); j++)
     {
     finale.get(i).add(smaller.get(i).get(j).split(","));
 
     }
 
 
     }
 
     for (int i =0; i < finale.size(); i++)
     {
     for (int j =0; j < finale.get(i).size(); j++)
     {
     for (int k =0; k < finale.get(i).get(j).length; k++)
     {
     System.out.println("MySet[" + i + "]["+j +"].get(" + k + ") = " +finale.get(i).get(j)[k]);
     }
 
 
     }
 
     }
 
     MySet[][] ms = new MySet[finale.size()][finale.get(0).size()];
 
     for (int i =0; i < finale.size(); i++)
     {
 
     for (int j =0; j < finale.get(i).size(); j++)
     {
 
     ms[i][j] = new MySet();
     for (int k =0; k < finale.get(i).get(j).length; k++)
     {
     if (finale.get(i).get(j)[k] != null && !finale.get(i).get(j)[k].equals(""))
     {
     ms[i][j].add(Integer.parseInt(finale.get(i).get(j)[k]));
 
     }
 
     }
 
     }
 
 
     }
 
     for (int i =0; i < ms.length; i++)
     {
     for (int j =0; j < ms[i].length; j++)
     {
     for (int k =0; k < ms[i][j].size(); k++)
     {
     System.out.println("ms[" + i + "]["+j +"].get(" + k + ") = "+ ms[i][j].get(k));
 
     }
     }
 
     }
 
     int startingState = s.nextInt();
     System.out.println("s:" + startingState);
 
     String fs = s.nextLine();
 
     if (fs.equals("") || fs == null)
     fs = s.nextLine();
 
     String[] firstHalf = fs.split("}");
 
 
      int temp = firstHalf[0].indexOf("{");
 
      String secondHalf = firstHalf[0].substring(temp+1);
 
      String[] finalHalf = secondHalf.split(",");
 
 
     ArrayList<Integer> finalState = new ArrayList<Integer>();
 
     for (int i =0; i < finalHalf.length; i++)
{
if (finalHalf[i] != null && !finalHalf[i].equals(""))
{
finalState.add(Integer.parseInt(finalHalf[i]));
}
 
}
 
System.out.println("Final state: " + finalState.toString());
 
try
    {
   s2  = new Scanner(new File(args[1]));
    }
 
    catch (ArrayIndexOutOfBoundsException aioobe)
    {
    System.out.println("Error!");
    System.exit(1);
 
    }
 
catch (FileNotFoundException fnfe)
    {
	System.out.println("Error!");
	System.exit(1);
 
    }
 
 
 
 
 
    }
 
    public static ArrayList<Integer>getFinalStateFrom(Integer state, Integer character)
    {
 
    ArrayList<Integer> al = new ArrayList<Integer>();
    return al;  // this is for now to get it to compile on all machines.  
 
 
 
 
 
 
    }
 
 
}

While I can find the next possible states without the lambda, i.e., the empty states, I need help with the lambda part. I'm going to show an output for a NFA and then show what the DFA conversion should look like. Actually, I might try it for at least two different files. However, this will take some time. I should be able to calculate them manually. Though it might take several minutes.

Ok, I still am confused about how the instructor got {0,2} but I seem to have gotten the other ones right.

 

6

  	a  	b

[a, b, ¸]

[0: 	{1}	{4} {2}, 1:	{5}	{2}	{}, 2:	{5}	{} {}, 3:	{}	{} {0}, 4:	{}	{1} {3}, 5:	{}	{} {4}]

0

 	{1}	{4} {2}

1

	{5}	{2}	{}

2

	{5}	{} {}

3

	{}	{} {0}

4

	{}	{1} {3}

5

	{}	{} {4}

MySet[0][0].get(0) = 1

MySet[0][1].get(0) = 4

MySet[0][2].get(0) = 2

MySet[1][0].get(0) = 5

MySet[1][1].get(0) = 2

MySet[1][2].get(0) = 

MySet[2][0].get(0) = 5

MySet[2][1].get(0) = 

MySet[2][2].get(0) = 

MySet[3][0].get(0) = 

MySet[3][1].get(0) = 

MySet[3][2].get(0) = 0

MySet[4][0].get(0) = 

MySet[4][1].get(0) = 1

MySet[4][2].get(0) = 3

MySet[5][0].get(0) = 

MySet[5][1].get(0) = 

MySet[5][2].get(0) = 4

ms[0][0].get(0) = 1

ms[0][1].get(0) = 4

ms[0][2].get(0) = 2

ms[1][0].get(0) = 5

ms[1][1].get(0) = 2

ms[2][0].get(0) = 5

ms[3][2].get(0) = 0

ms[4][1].get(0) = 1

ms[4][2].get(0) = 3

ms[5][2].get(0) = 4

s:0

Final state: [5]

             a     b      E
0          1      4      2
1          5      2      -
2          5      -      -
3          -      -      0
4          -      1       3
5          -      -       4
 
{0,a} = {1, 5, 4, 3, 0, 2}
{0,b} = {4, 3, 0, 2}
{0,E} = {2}
{1,a} = {5, 4, 3, 0, 2}
{1,b} = {2}
{1,E} = { }
{2,a} = {5, 4, 3, 0, 2}
{2,b} = { }
{2,E} = { }
{3,a} = { }
{3,b} = { }
{3,E} = {0, 2}
{4,a} = { }
{4,b} = {1}
{4,E} = {3, 0, 2}
{5,a}  = { }
{5,b} = { }
{5,E} = {4,3, 0, 2}
 
 
 
So final states so far of
{0,1,2,3,4,5}
{4 , 3, 0 ,2}
 
{{0,1,2,3,4,5},a} = {0, 1, 2, 3, 4, 5}
{{0,1,2,3,4,5},b}  = {0,1,2,3,4}
{{4,3,0,2}, a} = {0,1,2,3,4,5}
{{4,3,0,2},b} = {0,1,2,3,4}
{{0,1,2,3,4},a} = {0, 1, 2, 3, 4, 5}
{{0,1,2,3,4}, b} = {0,1,2,3,4}
 
final states so far:
{0,1,2,3,4,5}
{0,2,3,4}
{0,1,2,3,4}
 
{{0,1,2,3,4,5},E} = {2, 0, 3, 4}
{{0,2,3,4},E} = {0,3,2}
{{0,1,2,3,4|, E} = {0, 3, 2}
{{0,3,2},E} = {0,2}
{{0,2},E} = {2}
{{2},E} = { }

While I'm not again how to get the final state of {0,2}, I am thinking I'll need recursion in some places. Problem is, I'm not that great at recursion. I'll show the recursive steps to get that thing above. Just give me a bit.......

Here's some of it:

{0,a} = {1} Union (if Epsilon)  note 2 is skipped as there is no 'a' transition to it Union {5, through the a} Union {4} through Epsilon Union {3} through Epsilon Union {0} through Epsilon Union {2} through Epsilon.  = {1, 5, 4, 3, 0, 2}
{0,b} = {4} Union {3} through Epsilon Union {0} through Epsilon Union {2} through Epsilon (There is no way to b through the Epsilon at 0}.  = {4,3,0,2}
{1,a} = {5} Union {4} through Epsilon Union {3} through Epsilon Union {0} through Epsilon Union {2} through Epsilon = {5,4,3,0,2}
{1,b} = {2}
etc