Please enable JavaScript.
Coggle requires JavaScript to display documents.
Autómatas y Lenguajes Formales - Coggle Diagram
Autómatas y Lenguajes Formales
FUNDAMENTOS DE LA TEORIA
Símbolo
son representaciones icónicas que representan ideas o conceptos. Un símbolo es un signo
Ejemplo: A,B,C,D,E,F....Z Símbolos que representan las letras del abecedario.
Alfabeto
Conjunto finito, no vacío, cuyos elementos se denominan "letras" o "símbolos".
Ejemplo: Σ1={1,3,5,7,9...n} Alfabeto de números naturales impares
Cadena
Secuencia finita de letras formadas con los símbolos de un alfabeto.
Ejemplo: Σ2={0,1,2,3,..9} palabras sobre Σ2 49632, 78963, 741065.....n cadenas de caracteres sobre el alfabeto de los números naturales
Longitud de una Cadena
Número de símbolos o letras que componen una cadena o palabra.
Ejemplo: x=Abner =>|x|=5
Operaciones con cadena
Concatenación
Nuevo Lenguaje que esta compuesto al unir un lenguaje con otro, estos dos lenguajes pueden pertenecer a diferentes alfabetos.
Ejemplo: x={Abner], y={0101} => W(x ∩ Y)={λ,Abner0101}
Potencia
Operación de concatenar un lenguaje consigo mismo n veces
Ejemplo: sea x={Roberto} => x^2 = W(x)={λ,RobertoRoberto}
Inversa
Se denomina palabra refleja, inversa o palíndroma, que se puede leer de igual manera tanto de derecha a izquierda como de de izquierda a derecha.
Ejemplo: Ana, Radar, Reconocer, Otto, Oso.
Lenguaje
Se le denomina lenguaje sobre el alfabeto Σ a cualquier subconjunto del lenguaje universal W(Σ).
Ejemplo: La cadena vacía ´Ø´, es un subconjunto de cualquier Σ universal.
Lenguaje no vacío
Es aquella cadena que contiene como primer elemento a lambda,´λ´, este lenguaje es un subconjunto formado por cualquier Σ.
Ejemplo: A= {a] => W(A)= {λ,a,aa,aaa,aaaa,....}, y contiene un numero infinito de elementos.
Lambda
Es una letra del alfabeto griego y se usa como símbolo para representar lenguajes sobre cualquier alfabeto. Lambda representa una cadena vacía.
Ejemplo: B={1,0} => W(B)= {λ,0001,0101,1111,.....n}
Nombre: Abner Isaac Lázaro Ambrosio Carné: 5090-17-21662 Sección: C
Jornada: Sábados
