lenguajes formales 1

8/18/2019 LENGUAJES FORMALES 1

1/51

LENGUAJES

FORMALES


2/51

INTRODUCCION

- Lenguajes naturales

- Lenguaje es una forma de representar inform basada en un conjunto finito de signos o sím


3/51

- Lenguaje es una secuencia de fonemas o s- que forman sílabas, palabras, frases, párracapítulos, novelas, libros, bibliotecas etc.- que tiene una sintaxis

- que tiene una gramática- que tiene un estilo


4/51

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

interfaces, se quiere transmitir una semánti partir de un símbolo.


5/51

- Alfabeto: conjunto de símbolos que forma parte de un lenguaje.

- Sentencia o palabra o fórmula bien formasecuencia correcta de símbolos

- Lenguaje formal: lenguaje descrito media

un formalismo matemático; conjunto desecuencias de símbolos cuya construcciónconsigue con una gramática formal.


6/51

- Computar: procesar información

- Modelo de computación: máquina abstracque toma como entrada una secuencia desímbolos y los procesa. Dependiendo delmodelo, el resultado del cómputo puede se

- Una secuencia de acciones- Una salida expresada en un cierto lengu- Una respuesta de aceptación o rechazo d

la entrada


7/51

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

o biológico- Que en un punto de tiempo está en un e- Que dada una razón (por ejemplo una se

de entrada), cambia de estado

Ejemplos: reloj mecánico o electrónico,máquina para lavar, computador, el cerebro


8/51

- Autómata

- Modelo de computación- Máquina de estados- Funcionamiento basado en transicione

de estados

- Transiciones provocadas por la lecturade los símbolos de entrada


9/51

- Teoría de Autómatas

- Aplicación en diversos campos ya quese consideran los autómatas y lasmáquinas secuenciales como sistemascapaces de transmitir (procesar)

información, equiparable a cualquiersistema existente en la naturaleza.


10/51


11/51

- Informática: ciencia aplicada que abarca estudio y aplicaciones del tratamientoautomático de la información

- Informática teórica: disciplina que estudilas capacidades de los modelos decomputación y sus límites, así como eltipo de problemas que pueden tratar y laeficiencia con que pueden ser tratados.También es llamada TALF


12/51

HISTORIA


13/51


14/51


15/51


16/51


17/51


18/51


19/51


20/51


21/51


22/51


23/51


24/51


25/51


26/51

DEFINICIONES


27/51

ALFABETO

- Un alfabeto es un conjunto finito y no vacde elementos denominados símbolos.

- Se definen por extensión (enumeración desímbolos) o por comprensión (enunciando

alguna propiedad que todos los símbolosdeben cumplir)


28/51

ALFABETO

EjemplosΣ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, qs, 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


29/51

CADENA DE CARACTERES O PALABR

- Secuencia finita de símbolos seleccionadoalgún alfabeto o combinación de símbolos

Ejemplos

w = mar x = 010101y = a1a5a47


30/51

CADENA NULA O VACÍA

- Cadena que no posee símbolos, puedeconstruirse en cualquier alfabeto

ε

λ


31/51

LONGITUD DE UNA CADENA

- Número de posiciones ocupadas por símbodentro de la cadena

|ε|=0|λ |=0


32/51


Ejemplosw = mar |w|=3x = 010101 |x|=6

y = a1a5a47 |y|=3


33/51


EjemplosSi y=a1a2...an, x=a1a2...an bai Є Σ, b Є Σ,

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


34/51

Dado un alfabeto Σ, se define Σ n como econjunto de palabras de longitud n que s pueden construir con ese alfabeto. Así, pejemplo, siempre se cumple que sea cuasea el alfabeto Σ, Σ 0 = {λ }


35/51


36/51


37/51


38/51

- Si xy=w llamamos x prefijo de w, y sufijo- 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?


39/51


40/51


41/51

Ejercicios

- Si Σ={0,1} entoncesΣ1=Σ2=Σ3=

Σ =Σ1

??

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


42/51

• Estrella de Kleene (cierre reflexivo transiu operación asterisco sobre un alfabeto Σ

Conjunto de todas las cadenas que se puedenconstruir a partir de los símbolos del alfabeto

Σ*= Ui≥0 Σi


43/51

• Cierre transitivo (operación más)

Σ+= Ui>0 Σi

Entonces se puede deducir que Σ*

= {λ }+ Σ+

LENGUAJES


44/51


45/51


46/51


47/51


48/51


49/51


50/51

Ejercicios:


51/51

Ejercicios:1. Defina L1 como el lenguaje de todas las cadena

constan de n ceros seguidos de n unos para cua

n ≥ 02. Defina L2 como el conjunto de cadenas formadel mismo número de ceros que de unos

lenguajes formales 1

Documents