Automata

## Class Automaton

- java.lang.Object
- - Automata.Automaton

-     public class Automaton
      extends java.lang.Object

  This class can represent different types of automaton: deterministic/non-deterministic and/or automata with output/automata without output. There are also two special automata: true automaton, which accepts everything, and false automaton, which accepts nothing. To represent true/false automata we use the field members: TRUE_FALSE_AUTOMATON and TRUE_AUTOMATA.
  Let's forget about special true/false automata, and talk about ordinary automata: Inputs to an ordinary automaton are n-tuples. Each coordinate has its own alphabet.
  Let's see this by means of an example:
  Suppose our automaton has 3-tuples as its input:
  -The field A, which is a list of list of integers, is used to store the alphabets of all these three inputs. For example we might have A = [[1,2],[0,-1,1],[1,3]]. This means that the first input is over alphabet {1,2} and the second one is over {0,-1,1},...
  Note: Input alphabets are subsets of integers.
  -Each coordinate also has a type which is stored in T. For example we might have T = [Type.arithmetic,Type.arithmetic,Type.arithmetic], which means all three inputs are of type arithmetic. You can find out what this means in the tutorial. -So in total there are 12 = 2*3*2 different inputs (this number is stored in alphabetSize) for this automaton. Here are two example inputs: (2,-1,3),(1,0,3). We can encode these 3-tuples by the following rule:
  0 = (1,0,1)
  1 = (2,0,1)
  2 = (1,-1,1)
  ...
  11 = (2,1,3)
  We use this encoded numbers in our representation of automaton to refer to a particular input. For example we might say on (2,1,3) we go from state 5 to state 0 by setting d.get(5) = (11,[5]). We'll see more on d (transition function) -Now what about states? Q stores the number of states. For example when Q = 3, the set of states is {0,1,2}. -Initial state: q0 is the initial state. For example we might have q0 = 1. -Now field member O is an important one: O stores the output of an state. Now in the case of DFA/NFA, a value of non-zero in O means a final state, and a value of zero means a non-final state. So for example we might have O = {1,-1,0} which means that the first two states are final states. In the case of an automaton with output O simply represents output of an state. Continuing with this example, in the case of automaton with output, the first state has output 1, the second has output -1, and the third one has output 0. As you have guessed the output alphabet can be any finite subset of integers.
  We might want to give labels to inputs. For example if we set label = ["x","y","z"], the label of the first input is "x". Then in future, we can refer to this first input by the label "x".
  -The transition function is d which is a TreeMap> for each state. For example we might have d.get(1) = {(0,[0]),(1,[1,2]),...} which means that state 1 goes to state 0 on input 0, and goes to states 1 and 2 on 1,....
  Author:
    Hamoon

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `java.util.List<NumberSystem>` | `NS` Types of the inputs to this automaton.
    `java.util.List<java.lang.Integer>` | `O` State Outputs.
    `int` | `Q` Number of States.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Automaton()`
    `Automaton(boolean TRUE_AUTOMATON)` Initializes a special automaton: true or false.
    `Automaton(java.lang.String address)` Takes an address and constructs the automaton represented by the file referred to by the address
    `Automaton(java.lang.String regularExpression, java.util.List<java.lang.Integer> alphabet)` Takes a regular expression and the alphabet for that regular expression and constructs the corresponding automaton.
    `Automaton(java.lang.String regularExpression, java.util.List<java.lang.Integer> alphabet, NumberSystem numSys)`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `Automaton` | `and(Automaton M)`
    `void` | `applyAllRepresentations()`
    `void` | `bind(java.util.List<java.lang.String> names)`
    `void` | `bind(java.lang.String a)`
    `void` | `bind(java.lang.String a, java.lang.String b)`
    `void` | `bind(java.lang.String a, java.lang.String b, java.lang.String c)`
    `void` | `canonize()` Sorts states in Q based on their breadth-first order.
    `Automaton` | `clone()` returns a deep copy of this automaton.
    `Automaton` | `compare(Automaton W, java.lang.String operator)` The operator can be one of "<" ">" "=" "!=" "<=" ">=".
    `void` | `compare(int o, java.lang.String operator)` The operator can be one of "<" ">" "=" "!=" "<=" ">=".
    `void` | `draw(java.lang.String address, java.lang.String predicate)` Writes down this automaton to a .gv file given by the address.
    `boolean` | `equals(Automaton M)`
    `int` | `getArity()`
    `java.util.List<java.lang.String>` | `getLabel()` Default constructor.
    `Automaton` | `iff(Automaton M)`
    `Automaton` | `imply(Automaton M)`
    `boolean` | `isBound()`
    `void` | `not()`
    `Automaton` | `or(Automaton M)`
    `void` | `quantify(java.util.Set<java.lang.String> listOfLabelsToQuantify)` This method computes the existential quantification of this automaton.
    `void` | `quantify(java.lang.String labelToQuantify)`
    `void` | `quantify(java.lang.String labelToQuantify1, java.lang.String labelToQuantify2, boolean leadingZeros)`
    `void` | `reverse()` this automaton should not be a word automaton (automaton with output).
    `Automaton` | `to_dk_bricks_automaton()` Transform this automaton from Automaton to dk.bricks.automaton.Automaton.
    `void` | `write(java.lang.String address)` Writes this automaton to a file given by the address.
    `Automaton` | `xor(Automaton M)`

    - ### Methods inherited from class java.lang.Object

      `equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### NS

          public java.util.List<NumberSystem> NS

      Types of the inputs to this automaton. There are two possible types for inputs for an automaton:Type.arithmetic or Type.alphabetLetter. In other words, type of inputs to an automaton is either arithmetic or non-arithmetic. For example we might have A = [[1,-1],[0,1,2],[0,-1]] and T = [Type.alphabetLetter, Type.arithmetic, Type.alphabetLetter]. So the first and third inputs are non-arithmetic (and should not be treated as arithmetic). This type is useful in type checking. So for example, we might have f(a,b+1,c+1), where f is the example automaton. Then this is a type error, because the third input to f is non-arithmetic, and hence we cannot have c+1 as our third argument. It is very important to note that, an input of type arithmetic must always contain 0 and 1 in its alphabet.

    - #### Q

          public int Q

      Number of States. For example when Q = 3, the set of states is {0,1,2}

    - #### O

          public java.util.List<java.lang.Integer> O

      State Outputs. In case of DFA/NFA accepting states have a nonzero integer as their output. Rejecting states have output 0. Example: O = [-1,2,...] then state 0 and 1 have outputs -1 and 2 respectively.

  - ### Constructor Detail

    - #### Automaton

          public Automaton()

    - #### Automaton

          public Automaton(boolean TRUE_AUTOMATON)

      Initializes a special automaton: true or false. A true automaton, is an automaton that accepts everything. A false automaton is an automaton that accepts nothing. Therefore, M and false is false for every automaton M. We also have that M or true is true for every automaton M.
      Parameters:
        `TRUE_AUTOMATON` -

    - #### Automaton

          public Automaton(java.lang.String regularExpression,
                   java.util.List<java.lang.Integer> alphabet)
                    throws java.lang.Exception

      Takes a regular expression and the alphabet for that regular expression and constructs the corresponding automaton. For example if the regularExpression = "01*" and alphabet = [0,1,2], then the resulting automaton accepts words of the form 01* over the alphabet {0,1,2}.
      We actually compute the automaton for regularExpression intersected with alphabet*. So for example if regularExpression = [^4]* and alphabet is [1,2,4], then the resulting automaton accepts (1|2)*
      An important thing to note here is that the automaton being constructed with this constructor, has only one input, and it is of type Type.alphabetLetter.
      Parameters:
        `address` -
      Throws:
        `java.lang.Exception`

    - #### Automaton

          public Automaton(java.lang.String regularExpression,
                   java.util.List<java.lang.Integer> alphabet,
                   NumberSystem numSys)
                    throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### Automaton

          public Automaton(java.lang.String address)
                    throws java.lang.Exception

      Takes an address and constructs the automaton represented by the file referred to by the address
      Parameters:
        `address` -
      Throws:
        `java.lang.Exception`

  - ### Method Detail

    - #### getLabel

          public java.util.List<java.lang.String> getLabel()

      Default constructor. It just initializes the field members.

    - #### clone

          public Automaton clone()

      returns a deep copy of this automaton.
      Overrides:
        `clone` in class `java.lang.Object`
      Returns:
        a deep copy of this automaton

    - #### quantify

          public void quantify(java.lang.String labelToQuantify)
                        throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### quantify

          public void quantify(java.lang.String labelToQuantify1,
                      java.lang.String labelToQuantify2,
                      boolean leadingZeros)
                        throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### quantify

          public void quantify(java.util.Set<java.lang.String> listOfLabelsToQuantify)
                        throws java.lang.Exception

      This method computes the existential quantification of this automaton. Takes a list of labels and performs the existential quantifier over the inputs with labels in listOfLabelsToQuantify. It simply eliminates inputs in listOfLabelsToQuantify. After the quantification is done, we address the issue of leadingZeros or trailingZeors (depending on the value of leadingZeros), if all of the inputs of the resulting automaton are of type arithmetic. This is why we mandate that an input of type arithmetic must have 0 in its alphabet, also that every number system must use 0 to denote its additive identity.
      Parameters:
        `listOfLabelsToQuantify` - must contain at least one element. listOfLabelsToQuantify must be a subset of this.label.
        `leadingZero` - determines which of leadingZeros or trailingZeros should be addressed after quantification.
      Throws:
        `java.lang.Exception`

    - #### reverse

          public void reverse()
                       throws java.lang.Exception

      this automaton should not be a word automaton (automaton with output). However, it can be non deterministic.
      Throws:
        `java.lang.Exception`

    - #### and

          public Automaton and(Automaton M)
                        throws java.lang.Exception

      Parameters:
        `M` -
      Returns:
        this automaton and M.
      Throws:
        `java.lang.Exception`

    - #### or

          public Automaton or(Automaton M)
                       throws java.lang.Exception

      Parameters:
        `M` -
      Returns:
        this automaton or M
      Throws:
        `java.lang.Exception`

    - #### xor

          public Automaton xor(Automaton M)
                        throws java.lang.Exception

      Parameters:
        `M` -
      Returns:
        this automaton xor M
      Throws:
        `java.lang.Exception`

    - #### imply

          public Automaton imply(Automaton M)
                          throws java.lang.Exception

      Parameters:
        `M` -
      Returns:
        this automaton imply M
      Throws:
        `java.lang.Exception`

    - #### iff

          public Automaton iff(Automaton M)
                        throws java.lang.Exception

      Parameters:
        `M` -
      Returns:
        this automaton iff M
      Throws:
        `java.lang.Exception`

    - #### not

          public void not()
                   throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### equals

          public boolean equals(Automaton M)
                         throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### applyAllRepresentations

          public void applyAllRepresentations()
                                       throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### compare

          public Automaton compare(Automaton W,
                          java.lang.String operator)
                            throws java.lang.Exception

      The operator can be one of "<" ">" "=" "!=" "<=" ">=". For example if operator = "<" then this method returns a DFA that accepts x iff this[x] < W[x] lexicographically. To be used only when this automaton and M are DFAOs (words).
      Parameters:
        `W` -
        `operator` -
      Returns:
      Throws:
        `java.lang.Exception`

    - #### compare

          public void compare(int o,
                     java.lang.String operator)
                       throws java.lang.Exception

      The operator can be one of "<" ">" "=" "!=" "<=" ">=". For example if operator = "<" then this method changes the word automaton to a DFA that accepts x iff this[x] < o lexicographically. To be used only when this automaton is a DFAO (word).
      Parameters:
        `W` -
        `operator` -
      Throws:
        `java.lang.Exception`

    - #### write

          public void write(java.lang.String address)

      Writes this automaton to a file given by the address. This automaton can be non deterministic. It can also be a DFAO. However it cannot have epsilon transition.
      Parameters:
        `address` -
      Throws:
        ``

    - #### draw

          public void draw(java.lang.String address,
                  java.lang.String predicate)
                    throws java.lang.Exception

      Writes down this automaton to a .gv file given by the address. It uses the predicate that caused this automaton as the label of this drawing. This automaton can be a non deterministic automaton but cannot be a DFAO. In case of a DFAO the drawing does not contain state outputs.
      Parameters:
        `address` -
      Throws:
        `java.lang.Exception`

    - #### to_dk_bricks_automaton

          public Automaton to_dk_bricks_automaton()
                                           throws java.lang.Exception

      Transform this automaton from Automaton to dk.bricks.automaton.Automaton. This automaton can be any automaton (deterministic/non-deterministic and with output/without output).
      Returns:
      Throws:
        `java.lang.Exception`

    - #### canonize

          public void canonize()

      Sorts states in Q based on their breadth-first order. It also calls sortLabel(). The method also removes states that are not reachable from the initial state. In draw() and write() methods, we first call the canonize the automaton. It is also used in write() method. Note that before we try to canonize, we check if this automaton is already canonized.
      Throws:
        `java.lang.Exception`

    - #### bind

          public void bind(java.lang.String a)
                    throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### bind

          public void bind(java.lang.String a,
                  java.lang.String b)
                    throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### bind

          public void bind(java.lang.String a,
                  java.lang.String b,
                  java.lang.String c)
                    throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### bind

          public void bind(java.util.List<java.lang.String> names)
                    throws java.lang.Exception

      Throws:
        `java.lang.Exception`

    - #### isBound

          public boolean isBound()

    - #### getArity

          public int getArity()