LENGUAJES

FORMALES

INTRODUCCION

- Lenguajes naturales

- Lenguaje es una forma de representar información

basada en un conjunto finito de signos o símbolos.

- Lenguaje es una secuencia de fonemas o símbolos

- que forman sílabas, palabras, frases, párrafos,

capítulos, novelas, libros, bibliotecas etc.

- que tiene una sintaxis

- que tiene una gramática

- que tiene un estilo

- Aparecen más símbolos o iconos para simplificar

interfaces, se quiere transmitir una semántica a

partir de un símbolo.

- Alfabeto: conjunto de símbolos que forman

parte de un lenguaje.

- Sentencia o palabra o fórmula bien formada:

secuencia correcta de símbolos

- Lenguaje formal: lenguaje descrito mediante

un formalismo matemático; conjunto de

secuencias de símbolos cuya construcción se

consigue con una gramática formal.

- Computar: procesar información

- Modelo de computación: máquina abstracta

que toma como entrada una secuencia de

símbolos y los procesa. Dependiendo del

modelo, el resultado del cómputo puede ser:

- Una secuencia de acciones

- Una salida expresada en un cierto lenguaje

- Una respuesta de aceptación o rechazo de

la entrada

- Autómata: dispositivo mecánico o electrónico

o biológico

- Que en un punto de tiempo está en un estado

- Que dada una razón (por ejemplo una señal

de entrada), cambia de estado

Ejemplos: reloj mecánico o electrónico,

máquina para lavar, computador, el cerebro

- Autómata

- Modelo de computación

- Máquina de estados

- Funcionamiento basado en transiciones

de estados

- Transiciones provocadas por la lectura

de los símbolos de entrada

- Teoría de Autómatas

- Aplicación en diversos campos ya que

se consideran los autómatas y las

máquinas secuenciales como sistemas

capaces de transmitir (procesar)

información, equiparable a cualquier

sistema existente en la naturaleza.

- Teoría de Autómatas (aplicaciones)

- 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

- Reconocimiento de patrones

- Fisiología del sistema nervioso

- Traducción automática de lenguajes

- El “analizador léxico” de un compilador…

- Informática: ciencia aplicada que abarca el

estudio y aplicaciones del tratamiento

automático de la información

- Informática teórica: disciplina que estudia

las capacidades de los modelos de

computación y sus límites, así como el

tipo de problemas que pueden tratar y la

eficiencia con que pueden ser tratados.

También es llamada TALF

HISTORIA

DEFINICIONES

ALFABETO

- Un alfabeto es un conjunto finito y no vacío

de elementos denominados símbolos.

- Se definen por extensión (enumeración de sus

símbolos) o por comprensión (enunciando

alguna propiedad que todos los símbolos

deben cumplir)

ALFABETO

Ejemplos

Σ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r,

s, t, u, v, w, x, y, z} alfabeto latino

Σ = {0, 1} alfabeto binario

Σ = {ai | i Є I}, donde I es un conjunto finito,

como por ejemplo I = {x Є N | x > 0 ˄ x < 50}

CADENA DE CARACTERES O PALABRA

- Secuencia finita de símbolos seleccionados de

algún alfabeto o combinación de símbolos.

Ejemplos

w = mar

x = 010101

y = a1a5a47

CADENA NULA O VACÍA

- Cadena que no posee símbolos, puede

construirse en cualquier alfabeto

ε

λ

LONGITUD DE UNA CADENA

- Número de posiciones ocupadas por símbolos

dentro de la cadena

|ε|=0

|λ|=0

LONGITUD DE UNA CADENA

Ejemplos

w = mar |w|=3

x = 010101 |x|=6

y = a1a5a47 |y|=3

LONGITUD DE UNA CADENA

Ejemplos

Si y=a1a2...an, x=a1a2...anb

ai Є Σ, b Є Σ,

entonces |y|=n ˄ |x|=n+1

Dado un alfabeto Σ, se define Σ n como el

conjunto de palabras de longitud n que se

pueden construir con ese alfabeto. Así, por

ejemplo, siempre se cumple que sea cual

sea el alfabeto Σ, Σ 0 = {λ}

- Si xy=w llamamos x prefijo de w, y sufijo de w

- Si x es prefijo de w entonces |x|≤ |w|

- Si y es sufijo de w entonces |y|≤ |w|

- Si x es prefijo de w, y es sufijo de w, x=y,

entonces x = y = w, ¿es verdad?

Ejercicios

- Si Σ={0,1} entonces

Σ1=

Σ2=

Σ3=

Σ =Σ1 ??

- Si Σ={a,ab,aab} y w=aab → |w|=1 ó |w|=2 ??

• Estrella de Kleene (cierre reflexivo transitivo

u operación asterisco sobre un alfabeto Σ)

Conjunto de todas las cadenas que se pueden

construir a partir de los símbolos del alfabeto Σ

Σ*= Ui≥0 Σi

• Cierre transitivo (operación más)

Σ+= Ui>0 Σi

Entonces se puede deducir que Σ* = {λ}+ Σ+

LENGUAJES

Ejercicios:

1. Defina L1 como el lenguaje de todas las cadenas que

constan de n ceros seguidos de n unos para cualquier

n ≥ 0

2. Defina L2 como el conjunto de cadenas formadas por

el mismo número de ceros que de unos