• Author / Uploaded
• Akasha Z

Citation preview

INSTITUTO TECNOLÓGICO SUPERIOR DE MARTÍNEZ DE LA TORRE

LENGUAJES Y AUTÓMATAS I. TEMA1. INTRODUCCIÓN FORMALES.

A LA

TEORÍA

DE

INGENIERÍA EN SISTEMAS COMPUTACIONALES ALUMNO: MARTÍNEZ LUNA ARACELI -170I0168 DOCENTE: ING. FRANCISCO XAVIER YÁÑEZ BRINGAS MARTÍNEZ DE LA TORRE, VER A 16 DE NOVIEMBRE DE 2019.

LENGUAJES

Ejercicio 1: Dé ejemplos de cadenas sobre el lenguaje {casa, amarilla, es, carro, azul, y, son} 𝑤1 = 𝑐𝑎𝑠𝑎𝑎𝑚𝑎𝑟𝑖𝑙𝑙𝑎 𝑤2 = 𝑐𝑎𝑟𝑟𝑜𝑎𝑧𝑢𝑙 𝑤3 = 𝑐𝑎𝑟𝑟𝑜𝑦𝑐𝑎𝑠𝑎 𝑤4 = 𝑐𝑎𝑠𝑎𝑦𝑐𝑎𝑟𝑟𝑜𝑠𝑜𝑛𝑎𝑧𝑢𝑙

Ejercicio 2: Dé ejemplos de cadenas sobre el lenguaje {0,2,3,4,5,6,7,8,9} 𝑤1 = 023456 𝑤2 = 987654 𝑤3 = 999532 𝑤4 = 000123456

Ejercicio 3: Usando las definiciones, demuestre las siguientes proposiciones:  Para cualquier par de cadenas: 𝜌 y 𝛾 , se tiene que: |𝜌𝛾| = |𝜌| + |𝛾| Denotamos las cadenas 𝜌 y 𝛾 como: 𝜌 = 5381

donde

|𝜌| = 4

𝛾 = 10327

donde

|𝛾| = 5

Al concatenar dichas cadenas tenemos 𝜌𝛾 = 538110327

Entonces:

|𝜌𝛾| = |538110327| = 9

|𝜌| + |𝛾| = 4 + 5 = 9 = |𝜌𝛾| ∴ |𝝆𝜸| = |𝝆| + |𝜸|

 Para cualquier cadena 𝜔, se tiene que 𝜆𝜔 = 𝜔𝜆 = 𝜔. 𝜆 denota una cadena vacía sobre cualquier alfabeto. Concatenar 𝜆𝜔 o 𝜔𝜆 no afecta a 𝜔 pues es cadena vacía. Dada la cadena 𝜔 = 1234

Tenemos que: 𝜆𝜔 = 1234 = 𝜔𝜆 = ω

Ejercicio 4: Dé ejemplos de cadenas sobre el lenguaje {𝑁𝑈𝑀, +,∗, (, ) } 𝑤1 = 𝑁𝑈𝑀 = () 𝑤2 = () + 𝑁𝑈𝑀 𝑤3 = 𝑁𝑈𝑀 ∗ () + 𝑤4 = (∗ +)

Ejercicio 5: Sea 𝐴 =, {𝑎 𝑏}, encuentre 𝐴4 . 𝐴4 = {

𝑎𝑎𝑎𝑎, 𝑎𝑎𝑎𝑏, 𝑎𝑎𝑏𝑏, 𝑎𝑎𝑏𝑎, 𝑎𝑏𝑏𝑏, 𝑎𝑏𝑏𝑎, 𝑎𝑏𝑎𝑎, 𝑎𝑏𝑎𝑏, } 𝑏𝑎𝑏𝑎, 𝑏𝑎𝑏𝑏, 𝑏𝑎𝑎𝑏, 𝑏𝑎𝑎𝑎, 𝑏𝑏𝑎𝑏, 𝑏𝑏𝑎𝑎, 𝑏𝑏𝑏𝑎, 𝑏𝑏𝑏𝑏

Ejercicio 6: Sea 𝐴 = {𝑎}, encuentre 𝐴8 . 𝐴8 = {𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎} Ejercicio 7: Para cualquier A, ¿Qué es 𝐴0 ? ¿Qué es 𝐴1 ? 𝐴0 = {𝜆}

𝐴1 = 𝐴

Ejercicio 8: Si A = {a} encuentre 𝐴𝑛 𝐴𝑛 = 𝐴𝑛−1 ∗ 𝐴

Ejercicio 9: Dadas las siguientes afirmaciones indique si son falsas o verdaderas justificando su respuesta.  Dado un alfabeto A, el lenguaje 𝐴∗ siempre es infinito. Verdadero, puede ser infinito, se pueden formar cadenas con tantos símbolos tenga el alfabeto, así como n cantidad del mismo símbolo.  Dado un lenguaje L, se puede decir que siempre 𝜆𝜖𝐿 Falso, 𝜆 es una cadena vacía pero dentro de un lenguaje puede o no pertenecer.  Dado un lenguaje L, se puede decir que siempre 𝜆𝜖𝐿∗ . Verdadero 𝜆 es una cadena vacióa y 𝐿∗ es el conjunto de todas las cadenas sobre L, incluyendo la cadena vacía ∴ 𝜆𝜖𝐿∗

Ejercicio 10: Si ∑ = {𝑎, 𝑏, 𝑐} ,

𝐴 = {𝑎, 𝑎𝑏, 𝑎𝑐},

𝐵 = {𝑏, 𝑏 2 }, calcular:

a) 𝐴𝐵 = {𝑎𝑏, 𝑎𝑏 2 , 𝑎𝑏𝑏, 𝑎𝑏𝑏 2 , 𝑎𝑐𝑏, 𝑎𝑐𝑏 2 } b) 𝐵𝐴 = {𝑏𝑎, 𝑏𝑎𝑏, 𝑏𝑎𝑐, 𝑏 2 𝑎, 𝑏 2 𝑎𝑏, 𝑏 2 𝑎𝑐} Ejercicio 11: Si ∑ = {𝑎, 𝑏, 𝑐} ,

𝐴 = {𝑏𝑎, 𝑏𝑐},

𝐵 = {𝑏 𝑛 : 𝑛 ≥ 0}, calcular:

a) 𝐴𝐵 = [{𝑏𝑎} ∪ {𝑏 𝑛 : 𝑛 ≥ 0}, {𝑏𝑐} ∪ {𝑏 𝑛 : 𝑛 ≥ 0}] 𝐴𝐵 = {𝑎𝑏 𝑛+1 : 𝑛 ≥ 0, 𝑐𝑏 𝑛+1 : 𝑛 ≥ 0} 𝐴𝐵 = {𝑎𝑏 𝑛 : 𝑛 ≥ 1, 𝑐𝑏 𝑛 : 𝑛 ≥ 0} b) 𝐴𝐵 = [{𝑏 𝑛 : 𝑛 ≥ 0} ∪ {𝑏𝑎}, {𝑏 𝑛 : 𝑛 ≥ 0} ∪ {𝑏𝑐}] 𝐴𝐵 = {𝑏 𝑛+1 𝑎: 𝑛 ≥ 0, 𝑏 𝑛+1 𝑐: 𝑛 ≥ 0} 𝐴𝐵 = {𝑏 𝑛 𝑎: 𝑛 ≥ 1, 𝑏 𝑛 𝑐: 𝑛 ≥ 1}