# IN620
Build and run all examples (pushdown automaton, a<sup>b</sup>, bubble sort, test)  
```
make
```
build and run specific example  
```
make automaton
make bubble_sort
make a_pow_b
make test
```
## Assembly
### registries
+ in : input registry n, n integer (read only)
	* i@in, i@rn, i@on for indirections  
	i@rn input registry, address is the integer in rn work registry
+ rn : work registry n, n integer
	* r@in, r@rn, r@on for indirections
+ on : output registry n, n integer (write only)
	* o@in, o@rn, o@on for indirections
	 
### arithmetic instructions
+ ADD(r1, r2, r3)
+ SUB(r1, r2, r3)
+ MULT(r1, r2, r3)
+ DIV(r1, r2, r3)  

r3 = r1 OP r2  
r1, r2 can be integers instead of registries.
### control instructions
+ JUMP(z)  
	current instruction += z
+ JE(r1, r2, z)  
	if r1=r2 then JUMP(z)
+ JL(r1, r2, z)
	if r1>r2 then JUMP(z)

r3 = r1 OP r2  
r1, r2 can be integers instead of registries.

## Pushdown automaton
Input word = i0, I, K  
+ i0 total length of input word
+ I = i1, J
	* i1, size of automaton input word
	* J automaton input, list of integers
+ K, list of transitions
### transition (q, a, A, w, q')
+ q : state before
+ q' : state after
	* 0 : start state
	* 1 : accepting state
+ a : symbol in input
	* 2 : ε
+ A : symbol on stack (pop operation)
	* 2 : ε (no pop)
	* 3 : stack start symbol
+ w : word to push on stack  
	* w = u, V  
	  u : length of V, 0 if nothing to push  
	  V : list of integers to push (Vn, Vn-1... V0)  
	  Leftmost element of the list will be at the top of the stack after the transition (Vn here).
	  
output:
+ 0 : accept
+ 1 : reject

### examples :
transition (q, a, A, w, q') = (0, 3, 4, 54, 1)
```
(0, 3, 4, 2, 5, 4, 1)
```
transition (q, a, A, w, q') = (0, ε, 1, ε, 1)
```
(0, 2, 1, 2, 0, 1)
```
  
#### 0<sup>n</sup>1<sup>n</sup>
0<sup>n</sup>1<sup>n</sup> automaton:
```
(0, 0, 3, 2, 1, 3, 0)	// stack empty, read 0, push 1, stay in state 0
(0, 0, 1, 2, 1, 1, 0)	// stack with 1 on top, read 0, push 1, stay in state 0
(0, 1, 1, 0, 2)		// stack with 1 on top, read 1, pop 1, go to state 2
(2, 1, 1, 0, 2)		// stack with 1 on top, read 1, pop 1, stay in state 2
(2, 2, 3, 1, 3, 1)	// stack empty in state 2, go to accepting state
```  
#### 0<sup>n</sup>1<sup>n</sup> inputs

0<sup>n</sup>1<sup>n</sup>  
input 000111 (output should be 0)
```
(37, 6, 0, 0, 0, 1, 1, 1, 0, 0, 3, 2, 1, 3, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 2, 2, 1, 1, 0, 2, 2, 2, 3, 1, 3, 1)
```

0<sup>n</sup>1<sup>m</sup> n<m  
input 001111 (output should be 1)
```
(37, 6, 0, 0, 1, 1, 1, 1, 0, 0, 3, 2, 1, 3, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 2, 2, 1, 1, 0, 2, 2, 2, 3, 1, 3, 1)
```
0<sup>n</sup>1<sup>m</sup> n>m  
input 000011 (output should be 1)
```
(37, 6, 0, 0, 0, 0, 1, 1, 0, 0, 3, 2, 1, 3, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 2, 2, 1, 1, 0, 2, 2, 2, 3, 1, 3, 1)
```
!=0<sup>n</sup>1<sup>m</sup>  
input 001011 (output should be 1)
```
(37, 6, 0, 0, 1, 0, 1, 1, 0, 0, 3, 2, 1, 3, 0, 0, 0, 1, 2, 1, 1, 0, 0, 1, 1, 0, 2, 2, 1, 1, 0, 2, 2, 2, 3, 1, 3, 1)
```