lenguajes y autómatas: alfabetos, cadenas, lenguajes

7/25/2019 Lenguajes y autmatas: Alfabetos, cadenas, lenguajes

1/5

TECNOL GICO NACIONAL DE M XICOInstituto Tecnolgico de Tuxtla Gutirrez


2/5

Alfabeto

Conjunto finito y no vaci cuyos elementos se denominan smbolos. Se designanormalmente con la letra Ejemplo:

{0,1}{a,b,cx,y,z}{0,1,2,3,4,5,6,7,8,9}{a,b}

Conceptos

Palabra:es una secuencia finita de smbolos de un alfabeto, las misma se pueden crearespecificando un alfabeto determinado.Ejemplo:

Si el alfabeto es {a,b}:

Aba,bab,a,b,bbbbababababababababababababababbaba

Si el alfabeto es {0,1}

0,1,01,11,11,

Existe una palabra especial que representa una secuencia vaca de smbolos, y a menudose llama la palabra vaca, y se representa con la letra griega .

Subpalabras:subsecuencias de smbolos consecutivos de una palabra, a menudo seusan las palabras factor o infijo.

Ejemplo:

La palabra bbacontiene las siguientes subpalabras:

{,a,b,bb,ba,bba}

Es importante las palabras en negritas son tambin consideradas subpalabrasimpropias, las dems son palabras propias.

Prefijos:subpalabras al principio de una palabra.

Sufijos:subpalabras al final de una palabra.

Nota: la palabra vacia y entera se consideran sufijos y prefijos de cualquier palabra.Ejemplo:


3/5

Los prefijosde la palabras bbaab son {,b,bb,bba,bbaa,bbaab} se observam los prefijospropios en azul.

Los sufijosson {,b,bb,bba,bbaa,bbaab} se observan los sufijos propios en azul.

Cadenas

Una cadena o palabra sobre un alfabeto . admitimos la existencia de una nica cadenaque no tiene smbolos, la cual se denomina cadena vaca y se denota con . la cadenavaca desempea, en la teora de lenguajes formales, un papel similar al que desempeael conjunto vaco en la teora de conjuntos.

Longitud de cadena:es el nmero de smbolos que contiene. La notacin empleada es laque es la que se indica en el ejemplo:

Utilizamos las cadenas de los ejemplos:

I abcb I = 4,

I a + 2*b I = 5

I 000111 I = 6

I if a > b then a = b; I = 9

Cadena Vaca:es la nica cadena de caracteres de tamao cero. Y la podemos denotarusualmente con letras o (Griegas).

Concatenacin de cadenas:u y v, escrita uv, es "pegar" las dos cadenas para formaruna nueva.

Ejemplo:

Sea u = ab

v = ca

w = bb. Entonces

uv = abca

uw = cabb

(uv) w = abcabb

u(vw) = abcabb


4/5

El resultado de la concatenacin de u, v y w es independiente del orden en que lasoperaciones son ejecutadas. Matemticamente esta propiedad es conocida comoasociatividad.

Universo del discurso: es un conjunto de todas las cadenas donde podemos formar consmbolos del alfabeto V le denominamos universo del discurso de V y la representamos de

la siguiente manera W (V). Es evidente que W(V) es un conjunto infinito y que la cadenavaca pertenece a W(V).

Ejemplo:

Un afabeto con una sola letra V = { a }, podemos decir que el universo del discurso es:W(V) = { , a, aa, aaa, aaaa,....} y asi contiene una cadenas infinitas.

Lenguajes

Es un conjunto de cadenas, de todas las seleccionadas de un *. Donde determinado elalfabeto se denomina lenguaje. Si esun alfabeto y L *, entonces L es un lenguaje de .Observe que un lenguaje de no necesita incluir cadenas con todos los smbolos de , yaque una vez que hemos esta que L es un lenguaje de , tambin sabemos que es unlenguaje de cualquier alfabeto que sea un sper conjunto de .

La eleccin del trmino "lenguaje" puede parecer extraa. Sin embargo, los lenguajeshabituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el ingls,donde la coleccin de las palabras correctas inglesas es un conjunto de cadenas delalfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.

Tipos de lenguajes

Lenguaje natural (castellano): Nosotros estamos relacionados con el conceptotradicional de gramtica que, de esta forma intuitiva, podemos considerar un conjunto dereglas el cual nos indican que es correcto y que no lo es del, lenguaje natural. Con este finpodemos acrcanos a la definicin ms clara y formal de la lengua castellana.

Lenguaje artificial: En este lenguaje aplicamos el mismo mtodo en el cual definimos unfragmento del lenguaje de programacin. Donde pretendemos describir las instrucciones elcual nos permite asignar un valor a una expresin o a una variable en un lenguaje C.

Lenguaje regular: Llamamos as a los lenguajes porque sus palabras contienen"regularidades" o repeticiones de los mismos componentes, por ejemplo en este lenguajeL1 = { ab, abab, ababab, abababab,...} Este ejemplo podemos apreciar las palabras de L1son solo repeticiones de "ab" donde se repiten varias veces. Su regularidad consiste enlas palabras que contienen "ab" varias veces.

Herramientas computadoras ligadas con lenguajes.


5/5

Traductor: es un programa que tiene como entrada un texto escrito en un lenguaje(lenguaje fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto)que preserva el significado de origen.

Ejemplos de traductores son los ensambladores y los compiladores.

Compilador:es un programa informtico que traduce un programa escrito en lenguaje deprogramacin y lo pasa a lenguaje de programacin, podemos decir que este programanos permite traducir un cdigo fuente de un programa en lenguaje de nivel alto, y lopasmos a otro nivel inferior (lenguaje maquina).

Ensamblador: es el programa en que se realiza la traccin de un programa escrito enensamblador y lo pasa a lenguaje mquina. Directa o no directa la traduccin en que lasinstrucciones no son ms que instrucciones que ejecuta la computadora.

Intrpretes:son los que realizan normalmente dos operaciones:

Traducen el cdigo fuente a un formato interno. Ejecuta o interpretan el programa traducido al formato interno.

Donde la primera pertenece al interprete el cual llama a veces al compilador, as se generael cdigo interno, pero no es el lenguaje de mquina, ni lenguaje de smbolos, ni muchomenos un lenguaje de nivel alto.

lenguajes y autómatas: alfabetos, cadenas, lenguajes

Documents