Diagramas de sintaxis

Diagramas de sintaxis
Un segundo método alternativo para desplegar las
producciones de ciertas gramáticas es el diagrama de
sintaxis. Ésta es una imagen de la producciones que permite
al usuario ver las sustituciones en forma dinámica, es decir,
verlas como un movimiento a través del diagrama. En la
figura, se ilustrará los diagramas que resultan de la traducción
de conjuntos deproducciones típicos, que son, por lo general,
todas las producciones que aparecen en el lado derecho de
algún enunciado BNF.

a ) ::=

b) ::= | a | ab

c) ::= ab.

x

d) ::= ab | ab.

Componentes de un diagrama sintáctico
.

Ejemplo
.

Autómata finito
Un autómata finito o máquina de estado
finito es un modelo matemático de un
sistema que recibe una cadena
constituidapor símbolos de un alfabeto
y determina si esa cadena pertenece al
lenguaje que el autómata reconoce.

Definición formal
• Formalmente, un autómata finito (AF) puede
ser descrito como una 5-tupla (S, Σ, T, s, A):
• S un conjunto de estados;
• Σ Un alfabeto;
• T La función de transición: ;
• S Estado inicial;
• A Conjunto de estados de aceptación o finales

Formas de representar unautómata
finito
Además de notar un AF a través de su definición
formal es posible representarlo a través de otras
notaciones que resultan más cómodas. Entre
estas notaciones, las más usuales son:
• Las Tablas de Transiciones
• Los Diagramas de Transiciones

Ejemplo 1
•
•
•
•
•

S = {S1, S2},
Σ = {0,1},
T = {(S1,0, S2); (S1,1,S1); (S2,0,S1); (S2,1,S2)}
s = S1
A = {S1}.

Tablasde Transiciones

• La Tabla de Transición para el AF del
ejemplo 1 es
0

S1 S 2
S2 S 1

1

S1
S2

Los Diagramas de Transiciones
El Diagrama de transición para el AF del ejemplo 1 es:

Ejemplo 2
•
•
•
•
•

S = {S1, S2},
Σ = {a,b},
T = {(1,a,2); (2,b,3); (3,a,1); (1,b,3)}
s=1
A = No se dice.

Vale la pena destacar que formalmente la máquina de estado es la tuplaanterior y no el “dibujo”. Este es tan sólo una representación gráfica de la
máquina de estado para tener una más sencilla y rápida visualización de
su contenido.

SEMÁNTICA
Los nodos representan los posibles estados de aquello que se desea
modelar. Las etiquetas representan eventos que provocan un cambio. Las
aristas determinan de qué manera cada estado, dado un evento, deriva en
otro estado.Ejemplo 3
Supongamos que se quiere modelar el comportamiento de una puerta. La
puerta, inicialmente cerrada, puede pasar a estar abierta tras el evento
“abrir puerta”. Una vez abierta, puede pasar al estado cerrada, tras el
evento “cerrar puerta”.

Descripción informal de su funcionamiento
En el comienzo del proceso de reconocimiento de una cadena,
el AF se encuentra en el estadoinicial y a medida que procesa
cada símbolo de la cadena va cambiando de estado de acuerdo
a lo determinado por la función de transición. Cuando se ha
procesado el último de los símbolos de la cadena de entrada, el
autómata se detiene. Si el estado en el que se detuvo es un
estado de aceptación o final, entonces la cadena pertenece al
lenguaje reconocido por el autómata, caso contrario, lacadena
no pertenece a dicho lenguaje.

Trazas
El conjunto de posibles trazas correspondientes a una máquina
de estado finitos, se puede definir en término de grafos, cómo
el conjunto de todos los caminos (de ejes) alcanzables desde el
estado inicial.
Ejemplo
Las trazas de esta FSM son:
•{a, b, a} correspondiente a 1, 2, 3, 1
•{b, a} correspondiente a 1, 3, 1
•{a, b, a, b, a}correspondiente a 1, 2, 3, 1, 3, 1
•{b, a, a, b, a} correspondiente a 1, 3, 1, 2, 3, 1
•{b, a, b, a, ... , b, a} 1, 3, 1, 3, …, 1, 3
Etc…

Deadlock
• Formalmente hablando, una FSM tiene deadlock, si existe algún nodo
que no posea “salida” para ningún evento.
• Ejemplo
• El estado 2 no posee salida alguna,

Semántica del deadlock
La existencia de deadlock no necesariamente habla de un mal...