FA (RegAut API Specification)

java.lang.Object
- regaut.FA

All Implemented Interfaces:

java.lang.Cloneable
```
public class FA
extends java.lang.Object
implements java.lang.Cloneable
```
Deterministic finite state automaton. [Martin, Def. 2.11]

Field Summary

Fields
Modifier and Type	Field and Description
`java.util.Set<State>`	`accept` Accept states (A).
`Alphabet`	`alphabet` The automaton alphabet ().
`State`	`initial` Initial state (q₀).
`java.util.Set<State>`	`states` Set of `State` objects (Q).
`java.util.Map<StateSymbolPair,State>`	`transitions` Transition function ().

Constructor Summary

Constructors
Constructor and Description

FA()
Constructs an uninitialized FA.

FA(Alphabet a)
Constructs a new FA consisting of one reject state.

Constructors
Constructor and Description
`FA()` Constructs an uninitialized FA.
`FA(Alphabet a)` Constructs a new FA consisting of one reject state.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`accepts(java.lang.String s)` Runs the given string on this automaton.
`FA`	`checkWellDefined()` Checks that this automaton is well-defined.
`java.lang.Object`	`clone()` Clones this automaton.
`FA`	`complement()` Constructs a new automaton that accepts the complement of the language of this automaton.
`State`	`delta(State q, char c)` Looks up transition in transition function.
`State`	`deltaStar(State q, java.lang.String s)` Performs transitions in extended transition function.
`boolean`	`equals(java.lang.Object obj)` Checks whether the language of this automaton is equal to the language of the given automaton.
`java.util.Set<State>`	`findReachableStates()` Finds the set of states that are reachable from the initial state.
`java.lang.String`	`getAShortestExample()` Returns a shortest string that is accepted by this automaton.
`int`	`getNumberOfStates()` Returns number of states in this automaton.
`int`	`hashCode()` Computes hash code for this object.
`FA`	`intersection(FA f)` Constructs a new automaton whose language is the intersection of the language of this automaton and the language of the given automaton.
`boolean`	`isEmpty()` Checks whether the language of this automaton is empty.
`boolean`	`isFinite()` Checks whether the language of this automaton is finite.
`FA`	`minimize()` Constructs a new minimal automaton with the same language as this automaton.
`FA`	`minus(FA f)` Constructs a new automaton whose language is equal to the language of this automaton minus the language of the given automaton.
`FA`	`removeUnreachableStates()` Constructs a new automaton with the same language as this automaton but without unreachable states.
`void`	`setTransition(State q, char c, State p)` Sets a transition in the transition function.
`boolean`	`subsetOf(FA f)` Checks whether the language of this automaton is a subset of the language of the given automaton.
`java.lang.String`	`toDot()` Returns Graphviz Dot representation of this automaton.
`NFA`	`toNFA()` Converts this FA into an equivalent `NFA`.
`RegExp`	`toRegExp()` Converts this automaton into an equivalent `RegExp` regular expression.
`FA`	`union(FA f)` Constructs a new automaton whose language is the union of the language of this automaton and the language of the given automaton.

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - accept
```
public java.util.Set<State> accept
```
    Accept states (A). Subset of states.
  - alphabet
```
public Alphabet alphabet
```
    The automaton alphabet ().
  - initial
```
public State initial
```
    Initial state (q₀). Member of states.
  - states
```
public java.util.Set<State> states
```
    Set of State objects (Q).
  - transitions
```
public java.util.Map<StateSymbolPair,State> transitions
```
    Transition function (). This is a map from pairs of states and alphabet symbols to states (: Q Q).
- Constructor Detail
  - FA
```
public FA()
```
    Constructs an uninitialized FA. states and accept are set to empty sets, transitions is set to an empty map.
  - FA
```
public FA(Alphabet a)
```
    Constructs a new FA consisting of one reject state.
    
    Parameters:
    
    a - automaton alphabet
- Method Detail
  - accepts
```
public boolean accepts(java.lang.String s)
                throws java.lang.IllegalArgumentException
```
    Runs the given string on this automaton. [Martin, Def. 2.14]
    
    Parameters:
    
    s - a string
    
    Returns:
    
    true iff the string is accepted
    
    Throws:
    
    java.lang.IllegalArgumentException - if a symbol in s is not in the alphabet
  - checkWellDefined
```
public FA checkWellDefined()
                    throws AutomatonNotWellDefinedException
```
    Checks that this automaton is well-defined. In particular, this method checks that the transition function is total. This method should be invoked after each FA operation during testing.
    
    Returns:
    
    this automaton
    
    Throws:
    
    AutomatonNotWellDefinedException - if this automaton is not well-defined
  - clone
```
public java.lang.Object clone()
```
    Clones this automaton.
    
    Overrides:
    
    clone in class java.lang.Object
  - complement
```
public FA complement()
```
    Constructs a new automaton that accepts the complement of the language of this automaton. The input automaton is unmodified.
  - delta
```
public State delta(State q,
                   char c)
            throws java.lang.IllegalArgumentException
```
    Looks up transition in transition function.
    
    Returns:
    
    (q,c)
    
    Throws:
    
    java.lang.IllegalArgumentException - if c is not in the alphabet
  - deltaStar
```
public State deltaStar(State q,
                       java.lang.String s)
                throws java.lang.IllegalArgumentException
```
    Performs transitions in extended transition function. [Martin, Def. 2.12]
    
    Returns:
    
    *(q,s)
    
    Throws:
    
    java.lang.IllegalArgumentException - if a symbol in s is not in the alphabet
  - equals
```
public boolean equals(java.lang.Object obj)
```
    Checks whether the language of this automaton is equal to the language of the given automaton.
    
    Overrides:
    
    equals in class java.lang.Object
  - findReachableStates
```
public java.util.Set<State> findReachableStates()
```
    Finds the set of states that are reachable from the initial state. [Martin, Exercise 2.27(b)]
  - getAShortestExample
```
public java.lang.String getAShortestExample()
```
    Returns a shortest string that is accepted by this automaton.
    
    Returns:
    
    a (not necessarily unique) shortest example string, null if the language of this automaton is empty
  - getNumberOfStates
```
public int getNumberOfStates()
```
    Returns number of states in this automaton.
  - hashCode
```
public int hashCode()
```
    Computes hash code for this object. (When equals(Object) is implemented, hashCode must also be there.)
    
    Overrides:
    
    hashCode in class java.lang.Object
  - intersection
```
public FA intersection(FA f)
                throws java.lang.IllegalArgumentException
```
    Constructs a new automaton whose language is the intersection of the language of this automaton and the language of the given automaton. [Martin, Th. 2.15] The input automata are unmodified.
    
    Throws:
    
    java.lang.IllegalArgumentException - if the alphabets of f and this automaton are not the same
  - isEmpty
```
public boolean isEmpty()
```
    Checks whether the language of this automaton is empty. [Martin, Example 2.34]
  - isFinite
```
public boolean isFinite()
```
    Checks whether the language of this automaton is finite. [Martin, Example 2.34]
  - minimize
```
public FA minimize()
```
    Constructs a new minimal automaton with the same language as this automaton. [Martin, Sec. 2.6] The input automaton is unmodified. Note: this textbook algorithm is simple to understand but not very efficient compared to other existing algorithms.
  - minus
```
public FA minus(FA f)
         throws java.lang.IllegalArgumentException
```
    Constructs a new automaton whose language is equal to the language of this automaton minus the language of the given automaton. [Martin, Th. 2.15] The input automata are unmodified.
    
    Throws:
    
    java.lang.IllegalArgumentException - if the alphabets of f and this automaton are not the same
  - removeUnreachableStates
```
public FA removeUnreachableStates()
```
    Constructs a new automaton with the same language as this automaton but without unreachable states. The input automaton is unmodified.
  - setTransition
```
public void setTransition(State q,
                          char c,
                          State p)
```
    Sets a transition in the transition function. (q,c)=p
  - subsetOf
```
public boolean subsetOf(FA f)
```
    Checks whether the language of this automaton is a subset of the language of the given automaton. [Martin, Exercise 2.27(g)]
  - toDot
```
public java.lang.String toDot()
```
    Returns Graphviz Dot representation of this automaton. (To convert a dot file to postscript, run 'dot -Tps -o file.ps file.dot'.)
  - toNFA
```
public NFA toNFA()
```
    Converts this FA into an equivalent NFA. Note: this is trivial since an FA is just a special kind of NFA, except for the different representation.
  - toRegExp
```
public RegExp toRegExp()
```
    Converts this automaton into an equivalent RegExp regular expression. [Martin, Th. 3.30]
  - union
```
public FA union(FA f)
         throws java.lang.IllegalArgumentException
```
    Constructs a new automaton whose language is the union of the language of this automaton and the language of the given automaton. [Martin, Th. 2.15] The input automata are unmodified.
    
    Throws:
    
    java.lang.IllegalArgumentException - if the alphabets of f and this automaton are not the same
    
    See Also:
    
    NFA.union(regaut.NFA)

Class FA

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

accept

alphabet

initial

states

transitions

Constructor Detail

FA

FA

Method Detail

accepts

checkWellDefined

clone

complement

delta

deltaStar

equals

findReachableStates

getAShortestExample

getNumberOfStates

hashCode

intersection

isEmpty

isFinite

minimize

minus

removeUnreachableStates

setTransition

subsetOf

toDot

toNFA

toRegExp

union