MT

# 1 2 3 4 a b c # # # # # # # # # #
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
      ^
scriu X
=>

# 1 2 X 4 a b c # # # # # # # # # #
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
      ^


Mașina Markov:
intrarea este o secvență de simboluri


1 2 3 4 a b c

Reguli:
2 -> 555
4a -> 

=>
1 5 5 5 3 b c


vreau să specific:

"de fiecare dată când am un 2 urmat de două simboluri identice, încă un simbol, și apoi un a, aș vrea să fie înlocuită secvența cu doar cele 2 simboluri identice"

2 g1 g1 g2 a -> g1 g1

g - variabilă indică o legătură (un transfer) între diverse locuri din regulă.

=====================

Ab - alfabetul care conține șirurile care pot apărea în intrare și în ieșire.
Al - alfabetul de lucru - simboluri cu care pot să lucrez, dar nu apar în intrare și nu trebuie să apară în ieșire.
	* "variabile locale"
G - variabile generice -- variabile "adevărate"
	* au un domeniu
	* legate la momentul potrivirii regulii (potrivirii LHS)
	* trăiesc până la substituția RHS în șir
	* pentru
		* potrivirea unei valori oarecare
		* exprimarea unei legături între elemente din șablon
		* transferul valorii din LHS în RHS


========================

A = {1,2,3} B = {x, y, z}  Ab = A U B
Al = {a}

 1 2 y 2 z 3 3 1 x x 2 y
^

a 1 2 y 2 z 3 3 1 x x 2 y
--- g1 = 1

1 a 2 y 2 z 3 3 1 x x 2 y
  --- g1 = 2

1 2 a y 2 z 3 3 1 x x 2 y
    --- g2 = y

1 2 a 2 z 3 3 1 x x 2 y
    --- g1 = 2

1 2 2 a z 3 3 1 x x 2 y
      --- g2 = z

1 2 2 a 3 3 1 x x 2 y
...
1 2 2 3 3 1 2 a
              -
1 2 2 3 3 1 2
gata.

===================
În exemplu S15

11111 12x2y3 1111
      ------
g1=2
g2=3

11111 13x 1111


=====================

D O P

O D P

O P D

marker a - marchez simbolul pe care îl transport
marker b - marchez un simbol care a ajuns pe poziția finală