Project developed for the course of Algoritmi e Principi dell'informatica (Algorithms and Computer Science Principles) @ Politecnico di Milano (academic year 2017-2018). The course covered the fundamentals of algorithms, information theory, data structures and code optimization.
The project consists in developing a Non Deterministic Turing Machine using ANSII-C (no extra libraries allowed besides the standard one), following time and memory constraint imposed by professors. The implementation meets all the costraint and achieved a grade of 30L/30.
The code reads an input file with the following structure: (NB: this is a toy example, tests file contained thousands of input strings and transactions, I don't know the exact numbers since those files were private and only available to professors)
tr
1 a a R 1
0 x x R 0
0 y y R 0
0 a x R 1
0 a a L 7
0 c c R 7
0 b b R 7
1 y y R 1
2 _ _ R 0
0 _ _ L 3
3 y y L 3
3 x x L 4
4 x x L 4
2 a a L 2
2 b b L 2
2 x x L 2
2 y y L 2
1 b y L 2
4 _ _ R 5
6 _ _ S 7
7 _ _ S 7
acc
5
max
5000
run
bbbbbbbbbbbaaaaaaaaaaaaaaaaaaa
Where the tr section represents the transaction of our Turing Machine. Each transaction is composed by 5 elements (from left to right):
- Starting state
- Read input char
- Write char
- Move memory head (Left,Right, no movement)
- Next state
The acc section represents the accepting states.
max represents the maximum number of computations before stopping the simulation
run contains all the input string to be simulated.
The Turing Machine outputs 3 possible ending characters:
- 1 -> the simulation has ended on a accepting state for the given input string. NB: in order to accept, all the branches of the simulation must end on an accepting state
- 0 -> the simulation has ended on a NON accepting state. NB: it is sufficient to have a single non-accepting state to refuse the input string
- U -> Undefined, one or more of the branches has reached the maximum amount of allowed computation (specified inside
max), thus the output is unknown
Example of output:
0
0
1
U
0 ```