Regular Languages

Usage

Everything in the regular package is used for experimenting with regular languages through DFAs, NFAs, and regular expressions.

###Create Automata

Automata can be created in 3 different ways:

• Manually
• Regex String
• Regex Functions

There are also methods for creating other [basic automata](Basic Automaton).

####Manually

Manually creating an Automaton is the most difficult option of the three. You will need to make sure that both the State and Automaton objects are imported:

//imports
import edu.uab.cis.State
import edu.uab.cis.regular.Automaton

Next you will need to create the states that will be in your Automaton. I will just create a start and end state:

//Create states
val start: State = new State()
val end: State = new State()

Now we need transitions between the states. Transition are simply tuples containing the transitions start state, the character on which to transition, and the transitions end state. We will make a transition for the letter 'a' from our start state to our end state:

//Create Transitions
//Transitions are tuples: (StartState, Character, EndState)
val transition: (State, Char, State) = (start, 'a', end)

**Note:**If you would like to create an epsilon jump, you just have to transition on the null character '\0'.

Now we just create our Automaton object using our states and transitions. The constructor takes in a start state, a set of final states, and a set of transitions:

//Create Automaton
//This Automaton will accept only the character a
val automaton: Automaton = new Automaton(start, Set(end), Set(transition))

When the automaton is created, it will determine the alphabet of your automaton to be the set of all characters mentioned in the transitions it was given except for '\0'. It will also determine the set of all the states for the machine to be all of the reachable states from the start state.

####Regex String

You can also create an Automaton from regex as a string. You will need to import Automaton and BasicAutomaton.

//import
import edu.uab.cis.regular.Automaton
import edu.uab.cis.regular.BasicAutomaton

Then we can use the BasicAutomaton.regex() method to create our Automaton:

//Create Automaton
//This automaton accepts one or more a's followed by a b
val automaton: Automaton = BasicAutomaton.regex("(a+)b")

We can also create an Automaton from a regex string without importing BasicAutomaton:

val automaton: Automaton = "(a+)b"

This will implicitly convert the string to an Automaton.

####Regex Functions

The last way to create an Automaton is by using the regex functions. You will need to import Automaton and the functions in Regex:

//imports
import edu.uab.cis.regular.Automaton
import edu.uab.cis.regular.Regex._

The Regex object simply holds a list of methods for creating a basic automaton for each letter. This allows us to create our Automaton by putting a bunch of functions together in a way that feels like regex:

//Create Automaton
//This automaton is equal to the previous one
val automaton: Automaton = (a+)+b

Since we are just chaining a bunch of functions together, the second '+' is necessary.

###Run Automata

Automata can be tested by using the accepts() method:

//Using the automaton in the previous example:
automaton.accepts("ab")                //true
automaton.accepts("aaaaaaab")          //true
automaton.accepts("aaaa")              //false

Automata Closure Operations

We can easily apply many different closure properties and operations on our automata one they have been created:

• Concatenation
• Union
• Kleene/Repetitions
• Intersection
• Complement
• Subtraction
• Reversal
• Substitution

More detail on these operations can be found [here](Operations On Automata).

###Other Methods

An automaton is considered to be deterministic if it has no epsilon transitions and each of its states has exactly one transition for each letter in the automaton's alphabet:

automaton.isDeterministic()

If an automaton is not deterministic, we can use the getDFA() method. This method will return the automaton as a DFA relative to its alphabet:

automaton.getDFA()

We can get an automatons DFA relative to a given alphabet too:

automaton.getRelativeDFA(Set('a','b','c'))

An automaton is finite if it accepts a finite number of strings:

(a*).isFinite() //false
(a).isFinite()  //true

An automaton is empty if it accepts no strings:

automaton.isEmpty()

An automaton is total if its complement is empty:

(a*).isTotal() //true

We can also determine if an automaton only accepts the empty string:

((b*) intersect (a*)).isEmptyString() //true

Two automata are considered equal if they accept the same language:

automaton1 equals automaton2 //or
automaton1 == automaton2

An automaton is considered to be a subset of another automaton if its language is a subset of the other automaton's language:

(a).isSubsetOf(a*) //true
(a).isSubsetOf(a)  //true
(b).isSubsetOf(a*) //false