guia de teoria computacional



INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO
ESCOM




“GUÍA TEORÍA COMPUTACIONAL”



MATERIA:
Teoría Computacional



ALUMNO:
Martínez Rosales Pedro Balan



GRUPO:
2CV1



PROFESOR:
Yosafat Moscoso Malagon



FECHA ENTREGA:
9/Marzo/2012


















1.- ¿Qué es la teoría computacional?
R:
Ciencia de la computación ylas matemáticas que se encarga del estudio formal de los cómputos (obtención de una solución en el sentido matemático).

2.- ¿Qué es un alfabeto, que símbolo se utiliza para designarlo? Escribe un ejemplo:

R:
Un alfabeto es un conjunto finito, no vacío, sus elementos son llamados “símbolos”. Se define por la enumeración de los símbolos que contiene.

El símbolo griego que se utiliza paradesignar un alfabeto es Σ (Sigma).

El alfabeto de los números binarios: Σ={0,1}.

3.- ¿Qué es una palabra o cadena de caracteres?
R:
Es una secuencia de símbolos pertenecientes a un alfabeto y que es finito.

4.- Genera un par de palabras para los siguientes alfabetos:
R:
a. ∑1={A,B,C,D,…,Z}. X=JUAN Y= ANA Z=PEZ.
b. ∑2={0,1}. Y=10 Z=100 X=1000.
c.∑3={0,1,A,d} . Z=AdA X=01Ad Y=1001d.

5.- ¿A qué se le llama longitud de una palabra?
R:
Es el número de símbolos que componen una cadena o palabra.

6.- ¿Qué es la cadena vacía y como se representa?
R:
Es una cadena que no contiene símbolo alguno.
Se representa con los símbolos griegos, Épsilon (ε) o Lambda ( λ).

7.- Longitud y cardinalidad |w| y ||c||, Considerando elalfabeto ∑={d,e,f,j}
R:
i. |edefj|= 5
ii. |jefe|e= 2
iii. |deje|d= 1
iv. |jeje|j= 2
v. ||= 0
vi. ||= 0

8.- ¿Cómo se le llama al conjunto de todas las palabras que se pueden construir con las letras de un alfabeto∑? y ¿Cómo se designa?
R:
Se le llama lenguaje universal de Σ, y se denota como W(Σ). Siendo ) un conjunto infinito.

9.- ¿Cómo se le llama a un alfabeto de un únicosímbolo? Ejemplo: ∑={a} y Responde:
R:
a. ∑0={}
b. ∑1={a}
c. ∑4={aaaa, … ,aaaa} (16 veces aaaa)
d. ∑*=




A un alfabeto con un único símbolo se le llama también lenguaje generador de si mismo.


10.- Potencias de un alfabeto. Considera ∑={0,1}.
R:
a. ∑0={}
b. ∑1={0,1}
c. ∑3={000,001,010,011,100,101,110,111}

11.- Al conjunto de cadenas no vacías de un alfabeto se le designa como:R:
Cerradura Positiva.

12.- Responde: considerando ∑={a,b}
R:
a. ∑0={}.
b. ∑2={aa,ab,ba,bb}.
c. ∑+=∑1 U ∑2 U ∑3 U … ∑n = {a,b} U {aa,ab,ba,bb} U {aaa,aab,…,bbb} U … U{aaa…, … , …bbb}.
d. ∑*=∑+ U {}.

13.- Concatenar las siguientes cadenas: Sean x=01101 e y=110 Entonces:
R:
a. xy=01101110
b. yx=11001101
c. x=01101
d. xy=01101110
e. Demostrar que |xy|=|x|+|y|
|x|=5 e |y|=3xy=01101110
|xy|=8
|xy|=|x|+|y|
8 = 5+3
8=8. Identidad.

14.- Potenciar la siguiente cadena: Sea x=d3j
R:
a. x0= 
b. x1=d3j
c. x3=xxx=d3jd3jd3j
d. x-1= xR=j3d


15.- ¿Qué es un lenguaje y como se designa?
R:
Un lenguaje es un conjunto de palabras (cadenas) de un determinado alfabeto 𝛴, Formalmente, se llama lenguaje sobre un alfabeto a todo subconjunto del lenguaje universal de Σ.Y se denota como:
L⊂W(Σ)


16.- ¿Qué es una sub palabra o factor?
R:
Una subpalabra es aquella que tiene una secuencia en los símbolos iguales a la palabra, sin ser ella misma.
Ej: x=volar, subpalabra de x serian: vol, vo, olar, ar, , etc.





17.- Sea la palabra w=bacalao generar el conjunto de los prefijos y sufijos:
R:
Prefijos de w:
bacala
bacal
baca
bac
ba
bSufijos de w:
acalao
calao
alao
lao
ao
o

18.- ¿Qué es un factor propio? Y da un ejemplo:
R:
Son todos los prefijos y sufijos que no sean la cadena misma ni Lambda ( λ). Ej: los prefijos y sufijos del ejemplo anterior.

19.- ¿Es lo mismo el lenguaje vacío  que el lenguaje {}?
R:
No, ya que aunque el lenguaje vacio  y lenguaje {} son subconjuntos de W(Σ), la cardinalidad del...