SistemasFormales

Sistemas formales de Post
Roberto Moriyón

Sistemas Formales de Post
• Los introdujo Emile Post en la década de
1920 para estudiar propiedades de las
funciones computables
• Se utilizan como formalismo básico de la
Lógica Formal

Sistemas formales: Reglas
• Reglas de producción
– 

• Ejemplo (sistema MIU)
- xI  xIU
- xIIIy  xUy

// x,y(M+I+U)*

- Mx  Mxx
-xUUUy  xy

• Producción: Lo escribiremos usando 
– Ejemplo: MI  MIUIUIUIU
(MI  MIU  MIUIU  MIUIUIUIU)

Sistemas formales:
Aplicación de reglas
• AplRegla(u, v, c) = Aplica(Encaje(u, c), v)
• Ejemplo sencillo:
– xIIIy  xUy, MIIII  MUI, MIU

• Otro ejemplo:
– xIIIx  AxxxB, UUIIIUU  AUUUUUUB

Aplicación de reglas: Ejercicio
• [APLICA] Construir cuatro programas que
implementen lasfunciones encaje, aplica,
aplRegla y  anteriores, y otro que a
partir de una sucesión de especificaciones
de aplicación de la forma Ai  Bi
comprueba que mediante ellas se
consigue la producción    (sus tres
argumentos deben ser la especificación y
las cadenas  y )

Sistemas formales: Axiomas
• Los axiomas son cadenas de partida para
las cadenas producidas por el sistema
• Ejemplo: MI
• Sepuede generar MU a partir del sistema
anterior?

Sistemas formales: Axiomas
• Los axiomas son cadenas de partida para
las cadenas producidas por el sistema
• Ejemplo: MI
– MU no es producido por el sistema anterior
– Todas las cadenas producidas por el sistema
anterior tienen un número de Ies que no es
múltiplo de 3

• Ejercicio: Caracterizar las cadenas
producidas por el sistema anteriorSistemas formales:
Axiomas, II
• Los axiomas pueden ser conjuntos
infinitos si están definidos mediante
patrones u otros sistemas formales
• Ejemplo: El conjunto infinito de axiomas
xx se puede generar a partir de las reglas
– xx  0x0x

xx  1x1x

y de los axiomas
– 00

11

Sistemas formales: Ejemplos
• Dada una gramática hay un sistema formal
que genera el mismo lenguaje
Ejemplo:
S ::= aSb | bSa |SS
xSy  xaSby, xSy  xbSay, xSy  xSSy
• Generación a partir de símbolos iguales:
– En una gramática dos símbolos terminales
iguales pueden generar subpalabras distintas
– En un sistema formal dos variables de patrón
iguales dan lugar subpalabras iguales

Sistemas formales: Ejemplos, II
• Suma (x, y, z  -*)
– Regla: x+y=z  x+y-=z– Axiomas: x+=x

• Multiplicación (x, y, z  -*)
– Regla: x*y=z x*y-=zx
– Axiomas: x*=

Sistemas formales
• Las cadenas aceptadas por el sistema son
las producidas por sus reglas que tienen
determinados símbolos (alfabeto final)
• Por lo tanto, en un sistema formal hay que
decir qué cadenas pueden sustituir a las
variables y cuál es el alfabeto final
• Ejemplo: Números compuestos (números
que no son primos):

Sistemas formales: Ejemplo III
• Númeroscompuestos (x, y, z  -*)
– Reglas:
Las de la Multiplicación
x--*y--=z  Cz
– Axiomas: Los de la Multiplicación
– Alfabeto final: {C, -}

Sistemas formales: Reglas con
cabecera múltiple
Ejemplo:
• I  uvabuv
I  cuvd
xabx, cxd  exe
I  euve

Sistemas formales: Ejemplos, V
• No divide (x, y  -+)
– Regla: xNDy  xNDxy
– Axiomas: xyNDx
– Alfabeto final: {ND, -}

• Sin divisores menores no triviales(x, z  -+)
– Reglas:
Las de No divide
--NDz  zSDM--zSDMx , xNDz  zSDMx– Axiomas: Los de No divide
– Alfabeto final: {S, D, M, -} // Excluido el caso xSDM--

Sistemas formales: Ejemplos VI
• Ejemplo: 5 no tiene divisores menores que 4
--ND(A1)
--ND--(R1)
--ND----(R1)
-----SDM--- (R2)
[4]
---ND-(A1)
---ND----(R1)
[6]
-----SDM---- ([4], [6], R3)

Sistemas formales: Ejemplos VII
• Primo (x, y -+)
– Reglas:
Las de Sin divisores menores
zSDMz  Pz
– Axiomas:
Los de Sin divisores menores
P-– Alfabeto final: {P, -}

Reglas con patrones como
consecuentes
• Ejemplo:
xx  xy
• La variable de patrón y puede ser cualquier
cadena compatible con las restricciones
impuestas por el sistema
• Los axiomas se pueden escribir como reglas
sin antecedente (axioma)
• No es lo mismo que una regla con...

Leer documento completo

Regístrate para leer el documento completo.