Day: August 1, 2003

The following is a procedure for Maple that simulates a Markov chain by executing a specified number of trials:

MarkovSim := proc(Mat, startstage, ntrials)
  local count, nvisit, a, i, j, firstAbsorbingStage, run, stage, sumQuant;
  count:=Vector(ColumnDimension(Mat));
  nvisit:=Vector(ColumnDimension(Mat));
  firstAbsorbingStage:=0;
  for i from 1 to ColumnDimension(Mat) do
    for j from 1 to RowDimension(Mat) do
      if Mat[j,i]>=1.0 then firstAbsorbingStage:=i; break; fi;
    od;
    if firstAbsorbingStage>0 then break; fi;
  od;
  for i from 1 to ColumnDimension(Mat) do count[i]:=0; od;
  for run from 1 to ntrials do
    for i from 1 to ColumnDimension(Mat) do nvisit[i]:=0; od;
    nvisit[startstage]:=1;
    stage:=startstage;
    while stage
      a:=rand()/10.^12;
      sumQuant:=0;
        for i from 1 to RowDimension(Mat) do
        if a<(sumQuant+Mat[i,stage]) and a>sumQuant then
          stage:=i; nvisit[i]:=nvisit[i]+1; break;
        fi;
        sumQuant:=sumQuant+Mat[i,stage];
      od;
    od;
    count:=count+nvisit;
  od;
  printf("Average number of steps in different stages before absorption:\n");
  for i from 1 to firstAbsorbingStage-1 do printf("%g ", count[i]/ntrials); od;
  j:=0; printf("\n");
  for i from 1 to ColumnDimension(Mat) do j:=j+count[i]; od;
  printf("Average number of steps until absorption:\n %g", j/ntrials);
end proc:

Here is a program I wrote for my Foundations of Computing class in college (here’s the source code). The program can be used to visually design and test deterministic finite automata (DFAs) of arbitrary size and complexity.

To create a new DFA from scratch, select “File » New DFA” from the main menu. A new, blank DFA window will be displayed.

The first step in creating the DFA is to define the alphabet over which the DFA will operate. The alphabet can be constructed from any combination of subsets of ASCII characters. From the right-hand portion of the window, select the subset of ASCII characters to include in the alphabet, and click “Add.” For example, you can add “Letter,” which will make the alphabet contain all letters (a-z, uppercase and lowercase), or you can add “Lowercase,” which will make the alphabet contain only lowercase letters. You may also add individual characters from the list, for example if you want the alphabet to consist only of the letters “a” and “b.”

The second step in creating the DFA is to define the possible states that the machine can be in. To begin defining states, go to the “State Transitions” tab. The states are organized in a state transition table, as shown below. To add a state, click “Add State.” For each state, the program will generate fields for all items in the alphabet, as well as the end-of-string character. By double-clicking in a field, you can change the transition rule for that state and character. The first state you add will be the start state of the machine. The states are automatically numbered in ascending order.

At this point the DFA is complete, and ready to accept strings. To start testing strings, go to the “Test String” tab. In the top field, type in the string you want to test, and click “Test.” The program will then list the configuration sequence that results from testing the string, and will finally say whether the string was accepted or rejected.

The program also allows the user to save the DFA to a file. To save the DFA you are currently working on, select “File » Save DFA” from the main menu. You may then select the directory and the file name for the DFA. To open a saved DFA file, select “File » Open DFA” from the main menu, and browse for the DFA file that you want to open.