Diagramas de Estados

Visualización de los autómatas finitos utilizados en el proyecto

Diagrama de flujo del simulador

Descripción

Flujo general que sigue el simulador al evaluar una cadena: validación de alfabeto, inicialización del autómata, lectura símbolo a símbolo aplicando la función de transición y decisión final (aceptar/rechazar). El diagrama ayuda a relacionar la implementación con la especificación formal.

  1. Entrada: cadena de símbolos (p. ej. NSNS).
  2. Validar que todos los símbolos pertenecen a Σ del autómata seleccionado.
  3. Inicializar estado actual = q₀.
  4. Por cada símbolo: aplicar δ(actual, símbolo) → nuevo estado.
  5. Al finalizar: si estado ∈ F → ACEPTAR, sino → RECHAZAR. Mostrar traza y Diagrama de Chomsky.

Ver en el simulador: Ir al simulador (ancla del flujo)

Entrada: cadena Validar símbolos ∈ Σ Inicializar q = q₀ Bucle: leer símbolo → aplicar δ(actual, símbolo) → actualizar estado Estado ∈ F? RECHAZAR ACEPTAR

Tipo 3: Universos Estables (Regular)

Descripción

Universos que mantienen patrones repetitivos y predecibles. Características normales y estables que se repiten infinitamente.

Definición Formal:

  • Lenguaje: L₃ = (NS)*
  • Σ = {N, S} (N=Normal, S=Estable)
  • Reconocedor: Autómata Finito Determinista (AFD)
  • Complejidad: O(n) tiempo lineal

Tabla de Transición:

Estado N S
→ q₀ q₁ -
q₁ - q₀
q₀ q₁ START Lee N Lee S Aceptador Espera S

Ejemplos:

  • ✓ ε - Aceptada (cadena vacía)
  • ✓ NS - Aceptada (Normal-Estable)
  • ✓ NSNS - Aceptada (patrón repetido)
  • ✗ N - Rechazada (incompleto, falta S)
  • ✗ SS - Rechazada (no comienza con N)

Tipo 2: Universos Recursivos (Libre de Contexto)

Descripción

Universos con estructura balanceada y recursiva. Mundos dentro de mundos con simetría perfecta. Ejemplo: Fábrica de Mr. Meeseeks (Petición cumplida de forma balanceada).

Definición Formal:

  • Lenguaje: L₂ = { Rⁿ Cⁿ | n ≥ 1 }
  • Σ = {R, C} (R=Request, C=Complete)
  • Reconocedor: Autómata de Pila (AP)
  • Gramática: Libre de Contexto (CFG)

Tabla de Transición (Simplificada):

Estado R (Entrada) C (Entrada) Acción Pila
→ q₀ q₁ - PUSH(R)
q₁ q₁ q₂ PUSH(R) / POP()
* q₂ - q₂ POP()

Autómata de Pila

q₀ q₁ q₂ R AGREGAR R→AGREGAR C QUITAR C→QUITAR

Evolución de la Pila

Entrada: RRCC Pila vacía: [ ] Lee R → AGREGAR: R Lee R → AGREGAR: R R Lee C → QUITAR: R Lee C → QUITAR: [ ] ✓ ACEPTADA

Ejemplos:

  • ✓ RC - Aceptada (1 petición resuelta)
  • ✓ RRCC - Aceptada (2 peticiones balanceadas)
  • ✓ RRRRCCCCC - Aceptada (anidación profunda, 4 Rs y 4 Cs)
  • ✗ RRC - Rechazada (desbalanceado)
  • ✗ R - Rechazada (petición sin completitud)

Tipo 1: Universos Complejos (Sensible al Contexto)

Descripción

Universos donde las reglas dependen del contexto ambiental. Mutaciones biológicas y físicas que responden al entorno. Ejemplo: Universos tipo Cronenberg.

Definición Formal:

  • Lenguaje: L₁ = { Bⁿ Fⁿ Cⁿ | n ≥ 1 }
  • Σ = {B, F, C} (B=Biology, F=Physics, C=Context)
  • Reconocedor: Autómata Linealmente Acotado (ALA)
  • Gramática: Sensible al Contexto

Ejemplo de Regla Sensible al Contexto:

Regla Descripción
B → BB (contexto) La biología se duplica solo si hay contexto
F → FF (contexto) La física se transforma según el contexto
C → CC (contexto) El contexto se propaga y afecta todo
q₀ q₁ q₂ q₃ q₄ B →BB F →FF C →CC ✓ OK Las reglas dependen del CONTEXTO: cada símbolo se transforma según los anteriores

Ejemplos:

  • ✓ BFC - Aceptada (mutación simple balanceada: 1B, 1F, 1C)
  • ✓ BBFFCC - Aceptada (mutación triple simétrica: 2B, 2F, 2C)
  • ✓ BBBFFFCCC - Aceptada (Cronenberg extremo: 3B, 3F, 3C)
  • ✗ BBFCC - Rechazada (desbalanceado: 2B, 1F, 2C)
  • ✗ BFC - Aceptada (mínimo válido)

Tipo 0: Universos Caóticos (Turing-Completo)

Descripción

Universos altamente complejos con comportamiento impredecible. Múltiples paradojas temporales coexisten. Ejemplo: Infinite Ricks, Infinite Mortys, anomalías espacio-temporales.

Definición Formal:

  • Lenguaje: L₀ = Iⁿ Mⁿ Aⁿ Dⁿ (y superiores)
  • Σ = {I, M, A, D} (I=Infinite Ricks, M=Mortys, A=Anomalies, D=Dimensions)
  • Reconocedor: Máquina de Turing
  • Potencia: Turing-Completo - puede simular cualquier algoritmo

Transiciones de Turing (Conceptual):

Estado × Símbolo Acción
q₀, I Escribir I, mover →, q₁
q₁, M Escribir M, mover →, q₂
q₂, A Escribir A, mover →, q₃
q₃, D Escribir D, mover →, aceptar
CINTA INFINITA (Memoria Ilimitada) I M A D Cabezal q₀ q₁ q₂ q₃ q₄ Lee I Escr: I, → Lee M Escr: M, → Lee A Escr: A, → Lee D ✓ ACEPTAR Máquina de Turing: Puede leer, escribir y mover el cabezal en ambas direcciones infinitamente

Ejemplos:

  • ✓ IMAD - Aceptada (caos dimensional mínimo: 1 de cada)
  • ✓ IIMMAADD - Aceptada (paradoja cuádruple: 2 de cada)
  • ✓ IIIMMMAAADDD - Aceptada (tormenta temporal severa: 3 de cada)
  • ✗ IIMAD - Rechazada (desbalanceado)
  • ✗ IMADE - Rechazada (símbolo inválido E)

Indecidible: Fracturas de Tiempo (No Computable)

Descripción

Universos con paradojas lógicas autorreferentes que NO pueden ser analizadas algorítmicamente. Imposibles de clasificar de forma computable. Ejemplo: Cuarto de Fracturas de Tiempo.

Definición Formal:

  • Lenguaje: L∞ = Lenguaje Indecidible (No computable)
  • Σ = {P, T, C} (P=Paradox, T=Temporal-Loop, C=Contradiction)
  • Reconocedor: NO EXISTE - Demostrado imposible por Gödel y Turing
  • Razón: Reducción al Problema de la Parada (HALT problem)

Análisis de Paradojas:

Patrón Decidibilidad Interpretación
P (una sola) Parcialmente Decidible Paradoja aislada (controlable)
PP (múltiples) INDECIDIBLE Paradoja recursiva sin fin
PTC (autorreferencia) INDECIDIBLE Autorreferencia paradójica total (HALT equivalente)
⚠ ZONA INDECIDIBLE ⚠ P T C Paradoja Temporal-Loop Contradicción ¿? ¿? ∞ Loop ∞ Loop ∞ Loop PTC = Autorreferencia Total = HALT Problem

Ejemplos:

  • ⚠ P - Parcialmente decidible (paradoja única, aislada)
  • 🚫 PP - INDECIDIBLE (dos paradojas = recursión infinita)
  • 🚫 PTC - INDECIDIBLE (autorreferencia completa = HALT problem)
  • ✓ T - Decidible (solo temporal, no es paradoja)
  • ✓ C - Decidible (solo contradicción aislada)

Conceptos Clave de la Jerarquía de Chomsky

Tipo 3: Regular

Patrones simples reconocibles por AFD. Memoria finita, potencia limitada. Expresiones regulares.

Tipo 2: Libre de Contexto

Estructuras anidadas y recursivas. Autómata de pila. Más poder que regulares pero menos que contexto-sensibles.

Tipo 1: Sensible al Contexto

Reglas que dependen del contexto. Autómata linealmente acotado. Muy expresivo pero aún decidible.

Tipo 0: Turing-Completo

Máquina de Turing. Puede computar cualquier algoritmo. Decidible pero con complejidad variable.

Indecidible: NO Computable

Autorreferencia paradójica. Equivalente a Halting Problem. Imposible de resolver algorítmicamente.

Jerarquía Estricta

L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀ ⊂ L∞. Cada nivel contiene al anterior. Complejidad computacional creciente.