110 lines
2.9 KiB
Markdown
110 lines
2.9 KiB
Markdown
# 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)
|
|
``` |