A java library to simulate turing machines using automatons.
This project is a try to map the idea of turing machines using OOP
with java.
In general, turing machines are theoretical machines that can compute a bunch of different things, and actually can execute all computational software in it.
This idea, was postulated by Alan Turing
, considered one of the fathers of computer science, in its idea for solving the Entscheidungsproblem.
A turing machine can, as simple ways, have 2 parts:
infinite tape
: responsible for contain all the symbols, which arecommands
for the machine.reader head
: responsible for read and write in the tape based on the actual instruction.
Every time that the head pass through a symbol, it reads the symbol, and, based on the instruction for that symbol in that given state
, it writes another symbol and then the machine moves left
or right
, and it goes until the last symbol.
The common approach to see that, is using images like these ones:
However, a more mathematical way is representing it with an automaton.
The elements of this graph are:
- circles: representing the machine states
- arrows: representing the transitions between each state
- labels: are the commands for each transition. These commands follow this pattern: (read)/(instruction),(move).
- read: is the symbol that we expect to read
- instruction: what we do when a symbol is reached, (like
P
for print, or you can see this a symbol to rewrite the tape). - move: the direction that you'll follow in the tape (
LEFT/RIGHT
)
- two circles: the final state. If your program reach it after passing through all the symbols, your the given input is correct and the program executed successfully.
The head will read symbol-by-symbol following the label instructions. Case your input has a symbol that for the actual state doesn't have a transition for it, the program crashes
, so this input is not accepted by that given machine configuration.
for more details check:
For this project, the idea was to try to abstract all this into classes and objects, then gather all it together in a java-library.
For that was used:
Case you want to install it, check the gradle documentation.
For ASDF
users, I recommend you check these plugins:
For opensuse
users, I've left a script to install java
and setup the JAVA_HOME
, check it here.
The main structure has 3 elements:
These have the following methods:
method | arguments | returns |
---|---|---|
constructor | char read , char write , Direction direction , State next |
- |
getReadSymbol | - | char |
getAction | - | Action |
The direction type is an enum for LEFT
and RIGHT
enum Direction {
LEFT, RIGHT
}
to access it just use:
Direction.LEFT
or
Direction.RIGHT
The Action is an auxiliar class which keeps track of the metadata for a transition, containing:
char write; //symbol to be written
Direction direction; //the tape direction
State next; //the next state
boolean reachedFinal; //if the next state is in the final states set
The methods of Action
are:
method | arguments | returns |
---|---|---|
constructor | char read , char write , State next , boolean reachedFinal |
- |
getWrite | - | char |
getDirection | - | Direction |
getNext | - | State |
getReachedFinal | - | boolean |
method | arguments | returns | throws |
---|---|---|---|
constructor | String id |
- | - |
constructor | String id , ArrayList<Transition> transitions |
- | - |
constructor | String id , ArrayList<Transition> transitions , boolean firstState , boolean finalState |
- | - |
addTransition | Transition transition |
- | - |
setFinal | - | - | - |
setFirst | - | - | - |
isFinal | - | boolean |
- |
isFirst | - | boolean |
|
getId | - | String |
- |
test | char symbol |
Action |
TransitionNotFound |
The TransitionNotFound exception is for transitions that doesn't exist for a given input char.
method | arguments | returns | throws |
---|---|---|---|
constructor | State[] states , String tape |
- | FirstStateException , InvalidTape |
getTape | - | String |
- |
test | - | boolean |
TransitionNotFound |
The InvalidTape exception is raised when the given tape has no symbols into.
this is an example of a automaton architecture:
relative automaton:
Note that the &
marks the start of the tape and the n
in the code is the same as
This example searches for sequences as:
aaabbb
aabb
ab
and the input tapes looks like:
# code
&aabbn
# automaton
&aabbϵ
Note: There's an example code in /lib/src/test/examples/App.java check it out
To install the machine
library, follow the instruction at github packages, you may need maven for that.
You can also install maven as an ASDF
plugin:
After installing gradle and cloning this repo, you can run the tests by doing:
./gradlew test
You can also build the project by your own, using:
./gradlew build
To publish this package to a github package, you need to add a classic token
to you account, and grant the access to read and write packages, to do that take a look at: github article.
After that, export the GH_USERNAME
and the GH_TOKEN
to your environment variables, like:
export GH_USERNAME="username"
export GH_TOKEN="gh_token"
Also, you'll need a GPG
key to sign the package, follow the official instructions to ensure that.
Then, run the gradle publish
to publish to gh packages.
./gradlew publish
alternatively, you can pass the variables along with the gradlew
command:
GH_USERNAME="username" GH_TOKEN="gh_token" ./gradlew publish
If you want to help this project, feel free to create an issue, make some PRs and text with some other contributors at this repo. Fix some bugs, add features, fix typos and etc.
Remember to be kind with everyone!