Lenguajes automatas

Unidad VI Lenguajes autómatas
Un lenguaje (L) sobre un alfabeto (A) es una colección de palabras sobre A: denota el conjunto de todas las palabras sobra A. Así un lenguaje L es simplemente un subconjunto de A*
Alfabeto
Considere un conjunto A de símbolos no vacíos en que una palabra o cadena (W) sobre el conjunto A es una secuencia finita de sus elementos. Por ejemplo suponga el alfabeto A={a,b, c}
Entonces las siguientes secuencias son palabras sobre A
W1= ababb
W2= accbaaa
Cuando se analizan palabras sobre A a menudo A se denomina alfabeto y sus elementos son letras
También es posible abreviar las palabras como la notación siguiente
W1= a2= aa
W2= a3=aaa
La secuencia vacía de letras se denota € o д, también se denomina palabra vacía
El conjunto de todas las palabras sobre Ase denota por A*(que se lee como “A estrella”. La longitud de una palabra W1 se escribe |W| o ln |W|
A menos que se establezca otra cosa el alfabeto A es finito, los símbolos w, u, v se reservan para palabras sobre A y los elementos de A provienen de letras a, b, c
Concatenación
Considere 2 palabras w1 y w2 sobre el alfabeto A sobre el alfabeto A. la concatenación de w1 y w2 se escribe w1w2juntos es la palabra que se obtiene al escribir las letras de w1 seguidas de las letras w2 por ejemplo para las palabras anteriores se tiene
w2w1= accbaaababb
Así como ocurre con las letras para cualquier palabra W se define w2= ww
w22= w2w2= accbaaaaccbaaa
Resulta evidente que para palabras arbitrarias u, v, w las palabras uv(w) y u (vw) son idénticas, ya que consta solo de las letras escritasuna atravesó de otra.

Máquinas de estado finito
Las máquinas de estado finito son una herramienta muy útil para especificar aspectos relacionados con tiempo real, dominios reactivos o autónomos, computación reactiva, protocolos, circuitos, arquitecturas de software, etc.
El modelo de FSM (Finite State Machine) es un modelo que posee sintaxis y semántica formales y que sirve para representaraspectos dinámicos que no se expresan en otros diagramas.
Generar salida mediante las siguientes entradas
M= {S, I, O, f, g, S1}
S= {S0, S1}
I= {0, 1}
O= {a, b}
f(S1, 1)= S1; f(S1, 0) = S0 f
f(S0, 1)= S0; f(S0, 0)= S1
g(S1, 1)= a; g(S1, 0)= b g
g(S0, 1)= b; g(S0, 0)= a

| f | g |
S/I | 0 | 1 | 0 | 1 |
S1 | S0 | S1 | a | b |
S0 | S1 | S0 | b | a |Entrada: 0011
Estado | S1 | f(S1, 0)=S0 | f(S0, 0)= S1 | f(S1, 1)=S1 | f(S1, 1)=S1 |
Entrada | 0 | 0 | 1 | 1 | |
Salida | g(S1, 0)=a | g(S0, 0)= b | g(S1, 1)=b | g(S1, 1)=b | |

Entrada: 01011
Estado | S1 | f(S1, 0)=S0 | f(S0, 0)= S0 | f(S0, 0)=S1 | f(S1, 1)=S1 | f(S1, 1)=S1 |
Entrada | 0 | 1 | 0 | 1 | 1 | |
Salida | g(S1, 0)=a | g(S0, 1)= a | g(S0, 0)=b | g(S1, 1)=b | g(S1, 1)=b | |Generar salida mediante las siguientes entradas
M={S, I, O, f, g, S0}
S= {S0, S1}
I= {a, b}
O= {0, 1}
f(S0, a)= S1; f(S0, b)= S0 f
f(S1, a)= S0; f(S1, b) = S1
g(S0, a)= 1; g(S0, b)= 0 g
g(S1, a)= 0; g(S1, b)= 1
| f | g |
S/I | a | b | a | b |
S0 | S1 | S0 | 1 | 0 |
S1 | S0 | S1 | 0 | 1 |

b/0 a/0
S0 a/0 S1b/1
Entrada: aabba
Estado | S0 | f(S0, a)=S1 | f(S1, a)= S0 | f(S0, b)=S0 | f(S0, b)=S0 | f(S0, a)= S1 |
Entrada | a | a | b | b | a | |
Salida | g(S0, a)=1 | g(S1, a)= 0 | g(S0, b)=0 | g(S0, b)=0 | g(S0, a)=1 | |

Entrada: aaabbbaa
Estado | S0 | f(S0, a)=S1 | f(S1, a)= S0 | f(S0, a)=S1 | f(S1, b)=S1 | f(S1, b)= S1 |
Entrada | a | a |a | b | b | b |
Salida | g(S0, a)=1 | g(S1, a)= 0 | g(S0, a)=1 | g(S1, b)=1 | g(S1, b)=1 | g(S1, b)=1 |

Estado | f(S1, b)=S1 | f(S1, a)=S0 | f(S0, a)=S1 |
Entrada | a | a | |
Salida | g(S1, a)=0 | g(S0, a)= 1 | |

Entrada: bababab
Estado | S0 | f(S0, b)=S0 | f(S0, a)= S1 | f(S1, b)=S1 | f(S1, a)=S0 | f(S0, b)= S0 |
Entrada | b | a | b | a | b | a |
Salida | g(S0, b)=0 | g(S0,...