Write a Java program that takes as input a DFA M and an input string w, simulate

Question

Write a Java program that takes as input a DFA M and an input string w, simulates M on w, and outputs ACCEPT if M accepts w, and REJECT if M does not accept w.

You will assume that the alphabet is = {0,1} and that the DFA has at most 20 states. The states are labeled 1,2, …20. Suppose that the starting state is 1. In order to input the DFA you will do the following: • You will ask the user to enter the transition function (either you can prompt the user by asking questions of the type “enter the state M goes to from state 14 and symbol 1”, or the user will just enter a list of 3-tuples, where a 3-tuple has the form (old-state, symbol, new state).

• Next, you will ask the user to enter the set F of accepting states. Next you will ask the user to enter the input string w. Test your program with the DFA from Example 1.11, page 38 ( run that DFA on 3 strings that are accepted and 3 strings that are not accepted), and the DFA from Example 1.68 (a), page 76 ( run that DFA on 3 strings that are accepted and 3 strings that are not accepted). Turn in: •

The code of your program (should be well documented) • o A short description of your program (1 page should be enough), including a presentation of the data structures that you have used to represent the DFA and the input string w (probably some types of arrays or linked lists). • o 2- 3 printouts with the screens when you run the program.

Explanation / Answer

Code:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class DFA {

   int trans[][];

   boolean accpt[];

   int startState;

   public DFA(){

      trans = new int[20][2];

      accpt = new boolean[20];

      for (int i =0; i<20; i++)

          accpt[i] = false;

      startState = 1;

   }

   private void readTrans() throws IOException {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      System.out.println("Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)");

      String line = br.readLine();

      while (!line.equalsIgnoreCase("end")) { //you may need to change the termination condition

          String tokens[] = line.split(" ");

          trans[Integer.parseInt(tokens[0].trim())-1][Integer.parseInt(tokens[1].trim())] = Integer.parseInt(tokens[2].trim())-1; //populate the Trans matrix, row indicate present state, column indicate input symbol and data indicate next state

          line = br.readLine();

      }

   }

   private void readAccptStates() throws IOException {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      System.out.println("Enter Accept states seperated by comma:");

      String[] tokens = br.readLine().split(" ");

      for (String s:tokens)

          accpt[Integer.parseInt(s)-1] = true; //mark the accepted states

   }

   private boolean parse (String w) { //method to parse the word

      int state = startState - 1; //in java start array index starts from 0, so we need to substact 1

      for (int i=0; i<w.length(); i++)

          state = trans[state][w.charAt(i)-'0'];

      return accpt[state]; //return accepted state

   }

   public static void main(String[] args) throws IOException {

      DFA dfa = new DFA();

      dfa.readTrans();

      dfa.readAccptStates();

      System.out.println("Enter word: ");

      String word = new BufferedReader(new InputStreamReader(System.in)).readLine();

      if (dfa.parse(word))

          System.out.println("Accepted");

      else

          System.out.println("Not Accepted");

   }

}

OUTPUT:

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

01001011

Accepted

--------------------------------------------------------------------------------------------------------------------------------

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

0110000101

Accepted

---------------------------------------------------------------------------------------------------------------------------------

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

0111111111111

Accepted

-------------------------------------------------------------------------------------------------------------------------------------

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

1010101010101

Not Accepted

-------------------------------------------------------------------------------------------------------------------------------------

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

0000000000000

Not Accepted

--------------------------------------------------------------------------------------------------------------------------------------

Enter tuples in the form 'OLD STATE' 'SYMBOL' 'NEW STATE' (enter 'end' to stop)

1 0 1

1 1 2

2 0 1

2 1 3

3 0 3

3 1 3

end

Enter Accept states seperated by comma:

3

Enter word:

00000100000101010

Not Accepted

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.