Lenjuages automatas y criptologia

INSTITUTO TECNOLOGICO DE REYNOSA

CARRRERA:
ING. EN TECNOLOGIAS DE LA INFORMACION Y COMUNICACIÓN

MATERIA:
MATEMATICAS DISCRETAS II

ALUMNO:
GUILLERMO REYES MATA

PROFESOR:
JOSE MAXIMINO PIZANO LOPEZ

TEMA:
4.- LENGUAJES AUTOMATAS
5.-CRIPTOLOGIA

5 DE JUNIO DE 2012, CD, REYNOSA TAM.
UNIDAD 4 LENGUAJES AUTOMATAS
Lenguajes
Sea Σ una colección finita de símbolos.Este conjunto de símbolos se denomina alfabeto y los elementos letras. Una palabra sobre Σ es una cadena de longitud finita de elementos de Σ. La cadena vacía o cadena nula, denotada por ε, es una cadena que no contiene símbolos. El conjunto de todas las palabras sobre Σ se denota Σ∗. ε es una palabra en cualquier alfabeto Σ. Un lenguaje sobre Σ es un subconjunto de Σ∗. Si L denota el conjunto delos lenguajes sobre Σ se tiene que L = {L : L ⊂ Σ∗}
Note que ε, la cadena vacía, es la cadena que no contiene símbolos. Es diferente de ∅ el conjunto vacío (lenguaje vacío). Se sigue que {ε} es el conjunto que contiene exactamente una cadena, de hecho, la cadena vacía. La longitud de una palabra u ∈ Σ∗ ,denotada por |u|, es el número de posiciones que tiene la palabra. Se puede definir recursivamente de esta manera:
|ε| = 0 |ua| = |u| + 1

donde u ∈ Σ∗ y a ∈ Σ.
De este modo una palabra u ∈ Σ∗ se puede definir por una función u : {1, 2, . . . , |u|} → Σ donde u(i) esla letra que se encuentra en la posición i en la palabra u. Dos palabras u, v ∈ Σ∗ son iguales si |u| = |v| y u(i) = v(i) para 1 ≤ i ≤ |u|. Definimos una operación sobre Σ∗ denominada concatenación. Para u, v ∈Σ∗ la concatenación de u y v se denota uv y se define a través de la función uv : {1, 2, . . . , |u| + |v|} → Σ
uv(i) =½u(i), si 1 ≤ i ≤ |u|v(i − |u|), si |u| + 1 ≤ i ≤ |u| + |v|
Así la palabra uv es la palabra que se obtiene escribiendo las letras de u y luego las letras de v. Si u=u1u2 · · · uk y v = v1v2 · · · vs entonces uv = u1u2 · · · ukv1v2 · · · vs donde ui , vj ∈ Σ. Se deja al lector verificar que esta operación es asociativa.4.1 Maquinas 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 representar aspectosdinámicos que no se expresan en otros diagramas.
Sintaxis:
Las máquinas de estado finito se definen como una tupla S A S S sk , , , Σ ⊆ ×Σ× , donde:
• S = { s1,s 2, ,..., Sm}: es un conjunto finito de nodos.
• Σ : es un alfabeto finito de etiquetas.
• A: es un conjunto finito de aristas etiquetadas que unen nodos.
• sk ∈ S : es el estado inicial.
2

2

1

1

Ejemplo: a
•〈 S = {1,2,3}, b
• Σ = {a b, }, b
3

3

• A={(1,a,2),(2,b,3),(3,a,1),(1,a,3)}, a
• sk =1 〉

Vale la pena destacar que formalmente la máquina de estado es la tupla anterior 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
Semantica:
Los nodos representan los posiblesestados 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.
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...