On the Subject of Finite Automata

Hope you've studied state machines, or this bomb's state may transition to "exploded"

For this module, you will select one or more regexes based on the serial number, convert the regexes to finite automata, and apply operations to them. The first five screens display five regexes, and the last is the submission panel.

Terminology

• Regular expression (AKA regex): A string of text, consisting of the symbols a, b, ε (epsilon, representing a lack of text), and the operators listed below.
• Finite Automaton (plural: Finite Automata): A set of states and transitions between them, which can be converted to and from regexes. Each transition has an associated letter, which here must be either "a" or "b", used to control what input that transition is followed for.
• Transition Graph: A similar structure to a finite automaton, but the transitions can have any regex associated with them, not just "a" and "b". Used here as a step in the process of producing the finite automaton.

Order of operations for regular expressions, and syntax:

R and S represent any regexes

1. Parentheses: (R). Example: (a), (b)
2. Kleene star: R*. Example: a*, (ab)*
3. Concatenation: RS. Example: ab, ab*, b*a
4. Alternation: R|S. Example: a|b, a*|ab

Note that, in the last example for alternation, the operands are a* and ab, due to the order of operations. Similarly, in the last example for concatenation, the right operand is b*, and in the second Kleene star example, the operand is (ab). Also, note that, being a unary operator, * does not have a right operand, so b*a is a concatenation between b* and a

In the following algorithms, "outermost operation" means the last operation in the order of operations within the regex that is not inside parentheses. For instance, in the regex ab|a(ab*|a)b, the outermost operator is the alternation outside the parentheses, and the second-outermost operators are the concatenations outside the parethenses. In the case of a tie for lowest, either operation in the tie can be selected for the algorithm described on the next page.

Determining which regexes and operations to use

To determine which regex or regexes to use, look at the digits of the serial number.

If there is an odd number of digits in the serial number:

1. Divide the middle digit by 5.
2. The remainder is the regex to convert to a finite automaton.
3. If the middle digit of the serial number is 5 or higher, then take the complement of the resulting finite automata. If not, then the automata in the previous step is the final answer.

If there is an even number of digits in the serial number:

1. Divide the first digit and the last digit of the serial number by 5.
2. The remainders will be the two regexes to convert to finite automata.
3. If the first digit of the serial number is 5 or more, take the complement of the first automaton.
4. If the last digit of the serial number is 5 or more, take the complement of the second automaton.
5. If the last digit is smaller than the first, take the intersection of the two automata. Otherwise, take the union of the two. Either way, the result is the final answer.

The results will be entered into the module's table submission space, in a form as shown on the next page.

Converting regular expressions to finite automata

The process of converting a regular expression to a finite automaton is as follows:

• Create a new transition graph with two states and one transition, transitioning from a start state to a goal state on the full regex.
• (Optional) If, at any time, any two transitions have the same regex, origin, and destination, the duplicate can be removed.
• (Optional) If, at any time, any two states have all the same outgoing transitions with the same regexes and destinations, and either both of them or neither of them are goals, then you can take all transitions leading into one of the two, and make them instead lead into the other. Then the state you moved the transitions from can be removed.

Continued on next page...

• (Optional) If, at any time, any state has no possible paths along any number of transitions leading from it to a goal state, it can be removed.

• (Optional) Any unreachable state can be removed at any time.

  A state is "reachable" if there is a path along the transitions from a start state to that state. If not, it is "unreachable".

• While there are transitions for which the regex is not a, b, or ε:
  • Pick one of those transitions. Let's call it e.
  • Identify the outermost operation in the regex of e:
    • If the outermost operation in the regex is parentheses surrounding the whole expression, remove the parentheses and continue down this list.
    • If the outermost operation is a Kleene star R* of some regex R, do the following:
      1. Add a new state
      2. Connect from the source of e to the new state with an ε transition
      3. Connect from the new state to the destination of e with an ε transition
      4. Connect the new state to itself, with R as the transition
      5. Remove e
    • If the outermost operation in the regex is an alternation R|S of two regexes R and S, do the following:
      1. Replace e's regex with R
      2. Add a new transition from e's source to e's destination with regex S
    • If the outermost operation in the regex is a concatenation RS of two regexes R and S, do the following:
      1. Add a new state.
      2. Connect from e's origin to the new state with a new transition with regex R.
      3. Connect from the new state to e's destination with a new transition with regex S.
      4. Remove e.
• For each transition e with regex ε, do the following:
  1. Let A be the source of e, and let B be the destination.
  2. For each transition s which starts at B, add a copy of s which starts at A instead.

• 3. For each transition t which leads to A, add a copy of t which leads to B instead.
  4. If B is a goal state, then make A a goal state.
  5. Remove e.
• For each state S which still has multiple outgoing transitions with the same regex:
  1. Create a new state
  2. For each transition t starting at state S with that regex:
     • If t leads to a goal state, make the new state a goal
     • For each outgoing transition from t's destination, create a copy of it with the new state as its origin
  3. Remove all transitions starting at state S with that regex.
  4. Add a new transition with that same regex, going from S to the new state.
• If at least one state does not have both an outgoing a transition and an outgoing b transition:

1. Add a new state, which we will call B
2. Add an a transition and a b transition from B to itself.
3. For each state missing an a or b outgoing transition, add a new transition with that missing regex from that state to B

Operations on Finite Automata

There are three set operations that may be applied to finite automata. Below is a list of these, and how to evaluate them:

• Complement: For each state in the finite automaton this operation is applied to, toggle whether or not it is a goal state. Thus, all states, except the original goal states, are now goal states.
• Union:
  • Shortcut: If all states in one of the input automata are goal states or one input automata is the complement of the other, any finite automata with only goal states reachable will be accepted.
  • Shortcut: If one of the input automata has no accessible goal states, or both are equal, then the other input automata will be accepted.
  1. Create a new finite automaton. This automaton will have states correlating to pairs of states on the two finite automata this operation is applied to, which we will call "group states".
  2. Add a start group state to the new automaton. This correlates to the

• 2. pair of the two start states in the input finite automata.
  3. If either start state in the input automata is a goal state, the start group state is also a goal state.
  4. Follow the transitions from the corresponding states on each input automaton for both a and b, to find the states each input leads to.
     • We can label the group state by the number of the state in the two input DFAs which correlate to it. For instance, if a leaving state 1 in A and B goes to 2 and 3, respectively, then the output automaton has an a transition from 1,1 to 2,3.
  5. If there is no group state which correlates to this pair, add a new group state which correlates to that pair.
  6. If either state in the pair is a goal on its finite automaton, the group state is also a goal.
     • So, if state 3 in automaton B was a goal state, then group state 2,3 is also a goal state.
  7. If there is no transition connecting from the previous group state to this one with the corresponding regex, add such a transition.
     • In the above example, we would now add an a transition from group state 1,1 to group state 2,3
  8. Repeat this process from step 4 on for each new group state added, until there are no new group states left to process. Then, continue.
• 9. Rename the nodes to have numbers as their indices instead of pairs, replacing each instance of a particular pair with the corresponding number. This is the result DFA.

• Intersection:
  • Shortcut: If one of the input automata has no goal states, then any finite automata with no reachable goal states will be accepted.
  • Shortcut: If every state in one of the input automata is a goal state, then the result is equal to the other input automata.
  • Shortcut: If the input automata are equal, then the result is equal to them.
  • Shortcut: If the two input automata are complements of each other, then any finite automata with no reachable goal states will be accepted.
  1. Follow the same process as the Union process above, but only make a group state a goal state if both states in the pair are goal states.

Input format example

Consider a finite automaton with transitions between three states as shown below. Suppose state 1 is the start state, and state 3 is the goal state.

The following table shows the input format. The columns on the right indicate where the column's transition leads to from the row's origin state, which is listed in the column on the left.
The > before the number in the left column indicates the start state, and the + before the number in the left column indicates a goal state. If a state is both a start and a goal, it is indicated with >+ before the state number.

Origin State	a	b
>1	3	2
2	1	3
+3	2	1

Note that additional rows can always be added, but they cannot be removed. Rows with blank entries are ignored. To enter a number, click the cell to cycle current row numbers. To set a state as start or goal, click the state number in the first column. Use the up and down arrow to change which rows are visible.