LENGUAJES Y AUTÓMATAS resumido

INSTITUTO TECNOLOGICO DE CIUDAD JUAREZ








NOMBRE DE LA CARREA: Ingeniería En Sistemas Computacionales
NOMBRE DE LA MATERIA: Lenguajes Y Autómatas.
NOMBRE DEL DOCUMENTO: Apuntes 1era Unidad.
NOMBRE DEL ESTUDIANTE: Víctor Manuel Mendoza Arellano.
NOMBRE DEL PROFESOR (A): Martha Magdalena Hurtado Solís

18 de September de 2013



INDICE
Introducción de lenguajes yautómatas……………………………………………… 3
Que es lenguaje
Que es símbolo
Que es alfabeto
Gramática Lenguaje palabra y o cadena…………………………………………….. 5
Wurds……………………………………………………………………………….. 6
Tipos de gramáticas de Chomsky…………………………………………………… 6

Gramáticas de Estados Finitos ó Tipo 3
Gramáticas Independientes de Contexto ó Tipo2
Gramáticas Sensitivas al Contexto ó Tipo 1
Gramáticas de Estructura de Fraseó Tipo 0
Diagrama de fase de Compilación………………………………………………………………… 10
Conceptos de fases de Compilacion……………………………………………………………… 11


INTRODUCCIÓN
El estudio de la teoría de autómatas y de los lenguajes formales se puede ubicar en el campo científico de la Informática Teórica, un campo clásico y multidisciplinar dentro de los estudios universitarios de Informática. Es un campo clásicodebido no solo a su antigüedad (anterior a la construcción de los primeros ordenadores) sino, sobre todo, a que sus contenidos principales no dependen de los rápidos avances tecnológicos que han hecho que otras ramas de la Informática deban adaptarse a los nuevos tiempos a un ritmo vertiginoso. Es multidisciplinar porque en sus cimientos encontramos campos tan aparentemente dispares como lalingüística, las matemáticas o la electrónica.



INTRODUCCION LENGUAJES Y AUTOMATAS

¿Qué es Lenguaje?
Informalmente: un lenguaje es un conjunto de palabras o sentencias formadas sobre un alfabeto.
Cuando hablamos de lenguajes, ya sea de lenguajes naturales o de lenguajes de programación que son los conocidos por un estudiante de Computación, podemos tener alguna idea de los elementos que forman partede un lenguaje, estos conceptos son:

Símbolo: Representación de algo.
Ejemplos de símbolos:
letras (a, b, c, …, A, B, ...), dígitos(0, 1, 2, …), signos de puntuación( , . : ;), operadores matemáticos(+,-,*,/), signos de moneda ( $, £, €, ¥), signos especiales (@, #, %, &), símbolos patrios (bandera, himno nacional, escudo nacional), etc.

Alfabeto: Conjunto no vacío y finito desímbolos.

Ejemplos de alfabetos:
Alfabeto del español: A a, B b, C c, D d, E e, F f, G g, H h, I i, J j, K k, L l, M m, N n, Ñ ñ, O o, P p, Q q, R r, S s, T t, U u, V v, W w, X x, Y y, Z z
Alfabeto del griego: Α α
Alfa
Ι ι
Iota
Ρ ρ
Ro
Β β
Beta
Κ κ
Kappa
Σ ς
Sigma
Γ γ
Gamma
Λ λ
Lambda
Τ τ
Tau
Ε ε
Épsilon
Μ μ
Mi
Υ υ
Ipsilon
Δ δ
Delta
Ν ν
Ni
Φ φFi
Ζ ζ
Dseda
Ξ ξ
Xi
Χ χ
Ji
Η η
Eta
Ο ο
Omicron
Ψ ψ
Psi
Θ θ
Zeta
Φ φ
Pi
Ω ω
Omega






Los tipos de lenguaje son naturales y d programación y están formados por símbolos:





















Gramática: Define las reglas que permiten determinar cuáles palabras pertenecen a un lenguaje y cuáles no.
Ejemplos: gramática delespañol, gramáticas de Chomsky.


Lenguaje: Conjunto de palabras
Ejemplos: Lenguaje del español, lenguaje C, conjunto de palabras de as y bes que empiezan con a, etc.

Palabra o Cadena: Secuencia finita de símbolos de un determinado alfabeto.
Ejemplos:

Español: palabra, lenguaje, símbolo, niño.
Griego: αλφα, βετα, γαμμα, Δελτα.








El conjunto de reglas de producción debenser tales que generen las cadenas del lenguaje.

Primero la regla que genera una cadena de un wurd.

S W ( S produce W )

Luego una regla recursiva para generar cualquier cantidad de wurds, dos o más.

S SW ( S produce S W )

Ahora con la definición de wurd, obtenemos la siguiente regla:

W B ( W produce círculo vacío, B, círculo lleno )

Donde B, es el auxiliar...