INSTITUTO UNIVERSITARIO POLITÉCNICO"SANTIAGO MARIÑO"

EXTENSIÓN SAN CRISTÓBAL.

AMBAR STEPHANY LÓPEZ DUARTE

C.I. V-21.001.737ESCUELA ING. DE

SISTEMASESTRUCTURAS DISCRETAS

Y GRAFOSSAN CRISTÓBAL, 31 DE JULIO DE 2016

Lenguajes, Gramática y

Autómatas

información

Lenguaje

Forma de representar

A través de

signos o símbolos

Pueden ser un/una

Conjunto Secuencia

Sentencia

Alfabeto-Concatenación-Potencia -Reflexión

-Unión-Concatenación-Potencia-Clausura positiva-Cierre -Reflexión

Operaciones

Forma

Forma

Operaciones

Autómata

Máquina que imita la figura y los movimientos de un ser animado

Transiciones de estado

Se basa en

Lectura de entrada de símbolos

Provocadas por

• Teoría de la Comunicación.• Teoría de Control.• Lógica de los circuitos

secuenciales.• Ordenadores.• Teoría lógica de los sistemas

evolutivos y auto-reproductivos.• Reconocimiento de patrones.• Fisiología del sistema nervioso.• Traducción automática de

lenguajes.

Campos de aplicación

Gramática

Básica Formal

Estructura de frases y palabras de un

lenguaje

Cuádrupla de:–alfabeto de símbolos terminales–alfabeto de símbolos no terminales–axioma o símbolo inicial –conjunto finito de reglas de producción.

Alfabeto

A partir de un

Define

G0= Gramática que representa a lenguajes sin restricción.

G2= Gramática que representa a lenguajes independientes del contexto.

Derivaciones

Mediante

Se denomina

G1= Gramática que representa a lenguajes dependientes del contexto.

G3= Lineales

Por la izquierda Por la derecha

Lenguajes regulares

Clasificación según Chomsky