View on GitHub

Finite State Machine Utilities: Scala

Models of finite automata (DFA, NFA) with support of common operations and easily readable creation of concrete machines

Download this project as a .zip file Download this project as a tar.gz file

FSAUtils

Models of finite automata (DFA, NFA) with support of common operations and easily readable creation of objects.

The main goals of this project are:

Support of easily readable definitions of finite automata (FA) and regular expressions
Support of important basic operations on FA
Adherence to the following coding guidelines aiming to assure correctness:
- Simple and easily understandable code
- Mostly adherence to the functional programming paradigm
- Functional parts of the code (the core) closely follows abstract mathematical definitions of the respective operations

Features supported so far

Creation of Deterministic Finite Automata (DFA)
Creation of Nondeterministic Finite Automata (NFA)
Determinization of NFA
Creation of Regular Expressions (RE)
Checking for acceptance of a word by an automaton
Concatenation, Star, Union, Intersection, Complement for DFA/NFA
Checking DFA/NFA for equivalence
Implicit conversion of DFA to NFA
Pretty-printing toString methods for DFA/NFA
Determination of the language (RE) of a DFA/NFA
Conversion of RE to NFA (i.e. also checking of equivalence of DFA/NFA with RE)
Minimization of DFA
(De-)Serialization to and from XML

Get Started (1.1 Beta Version)

Prerequisites: You need to have Scala and the JVM installed. FSAUtils has been tested with Scala 2.11.2 and Java 1.7. Furthermore, the environment variable $SCALA_HOME has to be correctly set to the path where Scala resides.

The following steps should work for a Linux system.

Download the archive:

wget https://github.com/rindPHI/FSAUtils/archive/v1.1-beta.tar.gz -O FSAUtils-1.1-beta.tar.gz

Extract it:
```
tar xzf FSAUtils-1.1-beta.tar.gz
```
Build it:
```
cd FSAUtils-1.1-beta/
ant
```
As the result, you find a file "FSAUtils.jar" in the directory lib/ which you need to add to the classpath of scalac and scala in order to compile / run your objects that make use of FSAUtils.
In your Scala files, add the import
```
import de.dominicscheurer.fsautils._
```
and, if you want to use the FSA domain specific language for better readability, let your object extend FSA_DSL:
```
object MyObject extends FSA_DSL {
```

Compile your scala object:

scalac -classpath "/path/to/FSAUtils.jar" YourObject.scala

...and run it:

scala -classpath ".:/path/to/FSAUtils.jar" YourObject

An example file like mentioned in points 3. to 5. could have, for instance, the following content:

import de.dominicscheurer.fsautils._

object FSAUtilsTest extends FSA_DSL {

    def main(args: Array[String]) {
      val myDFA =
            dfa ('Z, 'S, 'q0, 'd, 'A) where
                'Z  ==> Set('a, 'b)   and
                'S  ==> Set(0, 1)     and
                'q0 ==> 0             and
                'A  ==> Set(0)        and
                'd  ==> Delta(
                      (0, 'a) -> 0,
                      (0, 'b) -> 1,
                      (1, 'a) -> 0,
                      (1, 'b) -> 1
                )|

        print("DFA accepts aaab: ")
        println(myDFA accepts "aaab")
        print("DFA accepts aaaba: ")
        println(myDFA accepts "aaaba")
    }

}

If you wish to run the included unit tests, execute

ant runTests

in the FSAUtils-1.1-beta directory.

Examples

Please consider the file Test.scala to see some working applied examples.

Creation of a DFA

val myDFA =
    dfa ('Z, 'S, 'q0, 'd, 'A) where
        'Z  ==> Set('a, 'b)   and
        'S  ==> Set(0, 1)     and
        'q0 ==> 0             and
        'A  ==> Set(0)        and
        'd  ==> Delta(
              (0, 'a) -> 0,
              (0, 'b) -> 1,
              (1, 'a) -> 0,
              (1, 'b) -> 1
        )|

print("DFA accepts aaab: ")
println(myDFA accepts "aaab")

Creation of an NFA

val myNFA =
    nfa ('Z, 'S, 'q0, 'd, 'A) where
        'Z  ==> Set('a, 'b)   and
        'S  ==> Set(0, 1)     and
        'q0 ==> 0             and
        'A  ==> Set(1)        and
        'd  ==> Delta(
              (0, 'a) -> Set(0, 1),
              (0, 'b) -> Set(0)
        )||

print("NFA accepts aaab: ")
println(myNFA accepts "aaab")

Star Operation for NFA

println((myNFA*) accepts "aaabaaab")

Determinization for NFA

println((myNFA toDFA) accepts "aaab")

Complement for DFA

println((!myDFA) accepts "aaab")

Concatenation

println(myNFA ++ myNFA2);

Pretty Printing

println(myNFA toDFA) yields:

DFA (Z,S,q0,d,A) with
|    Z = {a,b}
|    S = {{},{0},{1},{0,1}}
|    q0 = {0}
|    A = {{1},{0,1}}
|    d = {
|        ({},a) => {},
|        ({},b) => {},
|        ({0},a) => {0,1},
|        ({0},b) => {0},
|        ({1},a) => {},
|        ({1},b) => {},
|        ({0,1},a) => {0,1},
|        ({0,1},b) => {0}
|    }

Creation of RE

def myRegExp = (('a*) + ('b & ('b*) & 'a))* : RE

License

This file is part of FSAUtils.

FSAUtils is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

FSAUtils is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with FSAUtils. If not, see http://www.gnu.org/licenses/.