Unidad 1 Introducción Flashcards
Basicos
Alfabeto
un conjunto finito de símbolos denotados por Σ
Lenguaje formal
lenguaje artificial que consiste en palabras que siguen un conjunto de reglas específicas y están formadas por letras de un alfabeto
Período de los
Matemáticos Griegos Clásicos.
600 a.c. - 300 a.c.
Del período de los Matemáticos Griegos
Clásicos, uno de los más conocidos fue
Platón
El filósofo griego más representativo de
esta época es, sin lugar a dudas _______ quien propuso el
razonamiento deductivo a partir de los
silogismos aristotélicos
Aristóteles
surge la geometría de coordenadas (llamada Geometría Analítica) de René Descartes y el Cálculo Diferencial e
Integral de Gottfried W. Von Leibinz.
(1596-1650)
Formalización de las Matemáticas (Teoría
de Conjuntos)
(1821 - 1940)
Hilbert propuso el
algoritmo
Jerarquía de Chomsky…
Lenguajes Recursivos Ennumerables
Lenguajes Sensibles al Contexto
Lenguajes Libres de Contexto
Lenguajes Regulares
El enfoque de la Teoría de la Computación se
divide tradicionalmente en tres áreas:
Autómatas
Computabilidad
Complejidad
Teoría de Autómatas
Trata con definiciones y propiedades de
modelos matemáticos de computación.
modelo,
llamado gramáticas libres de contexto,
es usado en…
lenguajes de programación e
inteligencia artificial.
Un modelo llamado el
autómata finito, es usado en…
procesadores de texto, compiladores y
diseño de hardware.
Autómatas
ayudan a entender cómo funcionan las computadoras de manera formal y a aplicar esos conceptos a otras áreas de la informática.
Rusell:
Sea “C” el conjunto de todos los normales
Número de veces que cabe el en la
circunferencia
Galileo
Símbolo:
Unidad
básica que identifica de manera gráfica
una cosa.
Cadena:
Es una secuencia finita de
símbolos consecutivos
Prefijo
Agregar un conjunto de símbolos
a una cadena del lado izquierdo.
Alfabeto:
Un conjunto de símbolos
Concatenación:
Unión de 2 conjuntos de
cadenas.
Lenguaje:
Conjunto de Instrucciones,
símbolos y reglas que nos permiten tener
comunicación.
k copias de la cadena w
Potencia de Cadenas
Los ____ de una cadena están formados
por los primeros símbolos de ésta.
Prefijos
Los ___ de una cadena están formados por los
últimos símbolos de esta.
sufijos
es la imagen refleja de w. Por ejemplo, si w = ”able” entonces su inversa es “elba”.
Inversa
Conjuntos Normales
No se pertenecen a sí mismos
Conjuntos Extraños
Se pertenecen a sí mismos
El alfabeto de un lenguaje se
representa por
S
