1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                 
private enum States {

  Q0(false), Q1(false), Q2(true), Q3(true), Q4(false);

  final boolean accept;

  // Constructor for sate.
  // Every state is either accepting or not.
  States(boolean accept) {
    this.accept = accept;
  }

//...
}
              
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
                 
private enum States {

  Q0(false), Q1(false), Q2(true), Q3(true), Q4(false);

  States eyes;
  States smile;
  States sad;
  States space;

  static {
    Q0.eyes = Q1; Q0.smile = Q4; Q0.sad = Q4; Q0.space = Q0;
    Q1.eyes = Q4; Q1.smile = Q2; Q1.sad = Q2; Q1.space = Q4;
    Q2.eyes = Q4; Q2.smile = Q4; Q2.sad = Q4; Q2.space = Q3;
    Q3.eyes = Q1; Q3.smile = Q4; Q3.sad = Q4; Q3.space = Q3;
    Q4.eyes = Q4; Q4.smile = Q4; Q4.sad = Q4; Q4.space = Q4;
}

  States transition(char ch) {
    switch (ch) {
      case ':':
        return this.eyes;
      case ')':
        return this.smile;
      case '(':
        return this.sad;
      case '_':
        return this.space;
      default:
        throw new RuntimeException("Symbol is " +
           "not in the alphabet");
  }
}

//...
}
              
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
                 
private enum Alphabet {

  EYES, SMILE, SAD, SPACE
}

private enum States {

  //...

  States transition(Alphabet symbol) {
    switch (symbol) {
      case EYES:
        return this.eyes;
      case SMILE:
        return this.smile;
      case SAD:
        return this.sad;
      case SPACE:
        return this.space;
      default:
        return null;
    }
  }
}
              
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
                 
private enum States {

  //...

  static {
    Q0.eyes = Q1;  Q0.space = Q0;
    Q1.smile = Q2; Q1.sad = Q2;
    Q2.space = Q3;
    Q3.eyes = Q1; Q3.space = Q3;
  }

  States transition(char ch) {
    switch (ch) {
      case ':':
        return this.eyes == null? Q4 : this.eyes;
      case ')':
        return this.smile == null? Q4: this.smile;
      case '(':
        return this.sad == null? Q4: this.sad;
      case '_':
        return this.space == null? Q4: this.space;
      default:
        return Q4;
    }
  }

  //...
              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                 
public class DFA {

  private enum States {
    //...
  }

  public boolean accept(String string) {
    States state = States.Q0;

    for (int i = 0; i < string.length(); i++) {
      state = state.transition(string.charAt(i));
    }
    return state.accept;
  }
}
              
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
                 
private enum States {

  Q0(false), Q1(false), Q2(false), Q3(false), Q4(true);

  final boolean accept;

  States(boolean accept) {
    this.accept = accept;
  }

  Set<States> a;
  Set<States> b;

  static {
    Q0.a = new HashSet(Arrays.asList(Q1, Q2));
    Q0.b = new HashSet(Arrays.asList(Q4));

    Q1.a = new HashSet<>(Arrays.asList(Q0));
    Q1.b = Collections.EMPTY_SET;

    Q2.a = new HashSet<>(Arrays.asList(Q3));
    Q2.b = Collections.EMPTY_SET;

    Q3.a = Collections.EMPTY_SET;
    Q3.b = new HashSet<>(Arrays.asList(Q0));

    Q4.a = Collections.EMPTY_SET;
    Q4.b = Collections.EMPTY_SET;
  }

  Set<States> transition(char ch) {

    switch (ch) {
      case 'a':
        return this.a;
      case 'b':
        return this.b;
      default:
        return Collections.EMPTY_SET;
    }
  }
}
              
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
                 
public class NFA {

  private enum States {
  //...
  }

  // Accepts or rejects a string
  public boolean accept(String string) {
    Set<States> currStates = new HashSet<>();
    currStates.add(States.Q0);

    for (int i = 0; i < string.length(); i++)
      currStates = union(currStates, string.charAt(i));

    return currStates.stream().anyMatch(s -> s.accept);
  }

  // Helper method which returns set of next states
  private Set<States> union(Set<States> currStates, char ch) {
    Set<States> nextStates = new HashSet<>();

    for (States cState: currStates)
       nextStates.addAll(cState.transition(ch));

    return nextStates;
  }
}
              
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
                 
private enum States {

  Q0(true), Q1(false), Q2(false), Q3(false),
  Q4(false), Q5(true), Q6(false), Q7(true);

  final boolean accept;

  Set<States> a;
  Set<States> b;
  Set<States> epsilon;

  static {
    Q0.a = Collections.EMPTY_SET;
    Q0.b = Collections.EMPTY_SET;
    Q0.epsilon = new HashSet<>(Arrays.asList(Q1));

    Q1.a = Collections.EMPTY_SET;
    Q1.b = Collections.EMPTY_SET;
    Q1.epsilon = new HashSet<>(Arrays.asList(Q2, Q6));

    Q2.a = new HashSet<>(Arrays.asList(Q3));
    Q2.b = Collections.EMPTY_SET;
    Q2.epsilon = Collections.EMPTY_SET;

    Q3.a = Collections.EMPTY_SET;
    Q3.b = Collections.EMPTY_SET;
    Q3.epsilon = new HashSet<>(Arrays.asList(Q4));

    Q4.a = Collections.EMPTY_SET;
    Q4.b = new HashSet<>(Arrays.asList(Q5));
    Q4.epsilon = Collections.EMPTY_SET;

    Q5.a = Collections.EMPTY_SET;
    Q5.b = Collections.EMPTY_SET;
    Q5.epsilon = new HashSet<>(Arrays.asList(Q1));

    Q6.a = new HashSet<>(Arrays.asList(Q7));
    Q6.b = Collections.EMPTY_SET;
    Q6.epsilon = Collections.EMPTY_SET;

    Q7.a = Collections.EMPTY_SET;
    Q7.b = Collections.EMPTY_SET;
    Q7.epsilon = new HashSet<>(Arrays.asList(Q1));
  }

  States(boolean accept) {this.accept = accept;}

  Set<States> transition(char ch) {

    switch (ch) {
      case 'a': return this.a;
      case 'b': return this.b;
      default: return Collections.EMPTY_SET;
    }
  }
  //...
}
              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                 
private enum States {

  //...

  Set<States> eClose() {
    Set<States> states = new HashSet<>();
    states.add(this);

    for(States e: this.epsilon)
      states.addAll(e.eClose());

    return states;
  }
}
              
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
                 
public class eNFA {

  private enum States {...}

  public boolean accept(String string) {
    Set<States> currStates = new HashSet<>(States.Q0.eClose());

    for (int i = 0; i < string.length(); i++)
      currStates = union(currStates, string.charAt(i));

    return currStates.stream().anyMatch(s -> s.accept);
  }

  // helper method which returns set of next states
  private Set<States> union(Set<States> currStates, char ch) {
    Set<States> nextStates = new HashSet<>();

    for (States cState : currStates)
      for(States s: cState.transition(ch))
        nextStates.addAll(s.eClose());

    return nextStates;
  }
}