AUTOMATA1

L-SYSTEMS NO DETERMINISTAS

Al menos un símbolo tiene más de una producción.

Debe haber un mecanismo que selecciona uno de los productos para cada símbolo durante la derivación:

L-Systems Estocásticos

L-Systems Sensibles al contexto

L-Systems Paramétricos

L-Systems Estocásticos

Diferentes producciones para un símbolo son seleccionadas aleatoriamente.

Durante el reemplazo paralelo un nuevo número aleatorio es usado para cada símbolo.

Una probabilidad es asignada a cada producción.

Usado para generar variaciones entre individuos de una especie.

DEFINICION

Un L-System Estocástico es definido como G(π)={V,ω,P} dónde:

V: Alfabeto.

ω: Axioma.

P: Conjunto de producciones.

π.P→(0,1), llamada distribución de probabilidad, mapea el conjunto de producciones dentro del conjunto de probabilidades de producción. Para cualquier letra a∈V, la suma de probabilidades de todas las producciones con el mismo predecesor a es igual a 1.

La derivación μ⟹V es llamada una derivación estocástica en G(π) si para cada ocurrencia de la letra a en la palabra µ la probabilidad de la aplicación de las producciones P con el predecesor a es igual a π(P). Así, diferentes producciones con el mismo predecesor pueden ser aplicados a varias ocurrencias de la misma letra en un paso de derivación, causando diferentes salidas.

Las reglas no determinísticas son de la siguiente forma:

predecesor probabilidad % sucesor

Donde la aplicación de una regla u otra sobre un símbolo en la fase de reescritura depende de la probabilidad de ocurrencia asignada para cada regla.

Por ejemplo:

Alfabeto:

V:A B

Reglas de producción:

P1: A 70% AB

P2: B 30% BA

P3: B A

Axioma:

ω: A

Que puede producir para n pasos de derivación:

n=0 : A

n=1 : AB

n=2 : ABA

n=3 : BAAAB

n=4 : ABAABBAA

o:

n=0 : A

n=1 : BA

n=2 : AAB

n=3 : ABABA

n=4 : BAABAAAB

L-Systems Sensibles al contexto

La selección de una producción para un símbolo depende del símbolo adyacente en la cadena actual.

Una producción sensible al contexto se escribe como A^* 〈s〉 A^*→A^+, ejemplo:

...