Anexo 1 - Plantilla Tarea 1

Tarea 1: Fundamentación
Eliecer Guzmán Barrios

Alfabeto
El alfabeto es un conjunto finito y ordenado de letras
o símbolos, que es utilizado para representar el
lenguaje y convertirlo en un sistema de
comunicación.
S.f. Por Diccionario Actual. Desde https://diccionarioactual.com/abecedario/

Palabra o Cadena
En la teoría de los autómatas, la palabra se define como
una cadena finita formada por la concatenación de un
numero de símbolos.
La concatenación de dos cadenas u y v, escrita uv, es
"pegar" las dos cadenas para formar una nueva, por
ejemplo:
u = ab
v = ca
w = bb
Lenguaje
El lenguaje esta definido como un conjunto de palabras, también
llamadas cadenas, formado por símbolos en un alfabeto dado, el cual
puede ser finito o infinito.
Por ejemplo:
L = { ab, abab, ababab, abababab,...}

Lenguaje Regular
El lenguaje regular se define como aquel lenguaje cuyas palabras contienen
regularidades o repeticiones de los mismos componentes, por ejemplo:
L1 = { db, dbdb, dbdbdb, dbdbdbdb,...}

Expresión Regular
Las expresiones regulares son aquellas expresiones equivalentes algebraicas dentro de un
autómata. Donde estas solo son:
1. a ∈ Σ es una expresión regular
2. 2. ∅ es una expresión regular
3. 3. λ es una expresión regular
4. 4. Si α y β son expresiones regulares, entonces
a) α + β es una expresión regular
b) α · β (o αβ) es una expresión regular.
c) α ∗ es una expresión regular
d) (α) es una expresión regular
Por ejemplo:
Para Σ = {0, 1} tenemos las siguientes ExpRegs 0 1λ (0 + λ)11 ∗ 0 01 ( ∅ + 1)(1 + 0) ∗ 0
Expresión de conjunto:
Por extensión y por intensión
Por extensión: los conjuntos por extensión son una lista de elementos distinguidos entre llaves, es
decir, se define mediante sus elemento. Por ejemplo:
A= { a,b,c,d…z}
Por intensión: : los conjuntos por intensión son aquellos que se definen en base a sus
características. Por ejemplo:
A= { a:a es positivo}
A= { a:a es positivo y par }
Palabra nula o vacía λ
La palabra nula o vacia, es aquella palabra cuya longitud es cero, λ =0
– Sobre cualquier alfabeto es posible construir λ
– Utilidad de λ : será el elemento neutro en muchas operaciones sobre palabras y

lenguajes.
Operaciones regulares-
Unión
Dados dos lenguajes L1 y L2, su unión L1 U L2 contendrá todas las palabras que pertenezcan a
cualquiera de los dos lenguajes,
L1 U L2= { x tal que x ∈ L1 vx ∈ L2}
Por ejemplo: L1 = { nana, napa, lana} y

L2 = { O, nana, napa, pana, palabra, papa, pala}
L1 U L2= { O, nana, napa, lana, pana, palabra, papa, pala }
Concatenación
Si x e y son palabras, la concatenación, x.y es una palabra formada por los símbolos de x seguidos por los
símbolos de y
Por ejemplo:
Sea V = {0,1} alfabeto binario, sean v, w e y palabras de V*
Sean v=0111, w=1110
La palabra y= vw que leemos “v contatenado con w” queda: y = 01111110
Tengamos en cuenta, además, que la concatenación es una operación binaria y cerrada en el conjunto V*
Dados dos lenguajes L1 y L2, su concatenación, L1 . L2 contendrá todas las palabras que se puedan formar
por la concatenación de una palabra de L1 y otra de L2.
Por ejemplo: Dados L1 = { nana, napa, lana} y L2 = { O , nana, napa, pana, palabra, papa, pala} L1 . L2 =
{ nana, napa, lana, nananana, napanana, ...}
Estrella de Kleene
• La estrella de Kleene de cualquier lenguaje regular también es regular. Se caracteriza por que se utiliza solo un lenguaje en
lugar de dos. Se logra formando todas las concatenaciones de cero (cadena vacía) o más cadenas del lenguaje que se
amplía. La operación se representa con el asterisco supraíndice ( * ).
• Como se vio al principio de este apartado, la cadena vacía, l, no se consideraba como uno de los bloques de formación de
lenguajes, y es porque se genera a partir de Æ por medio de la estrella de Kleene; la cadena vacía pertenece a la estrella
de Kleene de cualquier lenguaje posible y por lo tanto debe pertenecer a Æ* y, por tanto, Æ**={l }.
• Para modificar el diagrama de transiciones, se coge el diagrama:
• Se añade un nuevo estado que va a ser el de inicio
• Este nuevo estado inicial también lo marcaremos como de aceptación (para que así puede aceptar la cadena vacía)
• Por cada uno de los arcos que hay desde el estado inicial original hacia otros (puede ser el mismo), se dibuja desde el
nuevo estado inicial un arco hacia el estado destino del arco correspondiente en el diagrama original y se etiqueta con el
mismo símbolo
• Desde cada estado de aceptación se dibuja un arco por cada uno de los que salen desde el estado inicial original hacia
otros (puede ser el mismo). Este sale hacia el estado destino del arco correspondiente que salía del estado inicial en el
diagrama original y se etiqueta con el mismo símbolo.
• Se quita la característica de inicio del estado inicial original.
Operadores
Un operador es un signo o símbolo que especifica el tipo de
cálculo que se realiza en una expresión. Hay operadores
matemáticos, de comparación, lógicos y de referencia. Access
admite diversos operadores, incluidos los operadores aritméticos
como +, -, de multiplicación (*) y división (/), además de los
operadores de comparación para comparar valores, los
operadores de texto para concatenar texto y los operadores
lógicos para determinar valores verdadero o falsos. En este
artículo se proporciona información sobre el uso de estos
operadores.
Procedencia de los
operadores
Como con otras álgebras, los operadores de las expresiones regulares tienen un orden de “precedencia”
prefijado, lo que significa que se asocian con sus operando en un determinado orden. El orden de precedencia
de los operadores es el siguiente:
1. El operador asterisco (*) es el de precedencia más alta. Es decir, se aplica sólo a la secuencia más corta
de símbolos a su izquierda que constituye una expresión regular bien formada.
2. El siguiente en precedencia es el operador de concatenación, o “punto”. Después de aplicar todos los
operadores * a sus operando, aplicamos los operadores de concatenación a sus operando. Es decir, todas las
expresiones yuxtapuestas (adyacentes sin ningún operador entre ellas). Dado que la concatenación es una
operación asociativa, no importa en qué orden se realicen las sucesivas concatenaciones, aunque si hay que
elegir, las aplicaremos por la izquierda.
3. Por último, se aplican todos los operadores de unión (+) a sus operando. Dado que la unión también es
asociativa, de nuevo no importa en que orden se lleven a cabo, pero supondremos que se calculan
empezando por la izquierda.
En ocasiones no se desea que una expresión regular sea agrupada según la precedencia de los operadores.
En dicho caso, se puede emplear paréntesis ( ) para agrupar los operando de la forma que se desee. Además,
nunca está de más encerrar entre paréntesis los operando que se quieran agrupar, incluso aunque la
agrupación deseada sea la prevista por las reglas de precedencia.
Conclusiones
Para poder comprender y aplicar los Autómatas y Lenguajes Formales, es necesario estudiar cada uno de los
elementos que se definen con anterioridad, los cuales hacen parte de la construcción de la construcción del
mismo. Cada uno de estos componente juega un papel muy importante en el campo de los Autómatas y
Lenguajes Formales, puesto que estos lo componen.
Créditos
Escuela: Ingeniería
Programa: Ingeniería de Sistemas
Nombre del estudiante: Eliecer Adolfo Guzmán Barrios
Año: 2022
UNAD
Referencias bibliográficas
Jurado, E (2008). TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES. Universidad de Extremadura. ESPACIO EUROPEO DE
EDUCACION SUPERIOR. Desde https://biblioteca.unex.es/tesis/Teorias_automatas.pdf
Martinez, E (2014). Teoria de Automatas & Lenguajes Formales. Desde https://
es.slideshare.net/buster_blader99/teoria-de-automatas-lenguajes-formales
Barron, C (S.f). Lenguajes y Autómatas. Desde https://academicos.azc.uam.mx/cbr/Cursos/UEA_14I_LenAut/LenAut_CBR_V1.pdf
S.f. LENGUAJES, GRÁMATICAS Y AUTÓMATAS. Universidad Tecnológica Nacional, Facultad Regional Buenos Aire. Tomado de file:///E:/
EAGB/Downloads/unidad_7_lenguajes_gramaticas_y_automatas.pdf
De la Fuente, R (1999). 1.6. EXPRESIONES REGULARES. Obtenido de http://www.aconute.es/computacion/automatasFinitos/ta_cap1_6.html
Tabla de operadores. Desde Access 2010. Microsoft. Desde https://
support.microsoft.com/es-es/office/tabla-de-operadores-e1bc04d5-8b76-429f-a252-e9223117d6bd
S.f. Expresiones Regulares . Desde https://
sites.google.com/site/wikiudocsctalf/home/vision-de-las-expresiones-regulares-y-lenguajes-regulares/expresiones-regulares
S.f. Teoría de Lenguajes Formales. Obtenido de https://sites.google.com/site/teoriadelenguajesformaless/1-4-tipos-de-lenguajes
Diaz. V, Cañante. J (2007). LENGUAJES FORMALES Y AUTOMATAS. Departamento de Lenguajes y Sistemas Informáticos. Escuela Técnica
Superior de Ingeniería Informática. Universidad de Sevilla. Obtenido desde http://www.lsi.us.es/docencia/get.php?id=5826
Padilla, G (2005). Alfabetos, cadenas y lenguajes. Obtenido desde http://delta.cs.cinvestav.mx/~
mcintosh/comun/summer2006/algebraPablo_html/node4.html

Anexo 1 - Plantilla Tarea 1

Cargado por

Copyright:

Formatos disponibles

Anexo 1 - Plantilla Tarea 1

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Anexo 1 - Plantilla Tarea 1

Cargado por

Copyright:

Formatos disponibles

Tarea 1: Fundamentación

Eliecer Guzmán Barrios

S.f. Por Diccionario Actual. Desde https://diccionarioactual.com/abecedario/

L = { ab, abab, ababab, abababab,...}

L1 = { db, dbdb, dbdbdb, dbdbdbdb,...}

– Sobre cualquier alfabeto es posible construir λ

– Utilidad de λ : será el elemento neutro en muchas operaciones sobre palabras y

L1 U L2= { x tal que x ∈ L1 vx ∈ L2}

Por ejemplo: L1 = { nana, napa, lana} y

También podría gustarte