Lenguajes y automatas

SEP SNEST DGEST

INSTITUTO TECNOLOGICO DE TOLUCA.

INGENIERIA MECATRONICA.

PROGRAMACIÓN EN TIEMPO REAL.

INVESTIGACIÓN UNIDAD IV: LENGUAJES Y AUTÓMATAS.

ÍNDICE

Unidad IV: lenguajes y autómatas.

4.1 Introducción a lenguajes y autómatas.
4.2 Circuitos secuenciales y máquinas de estado finito.
4.3 Autómatas de estado finito.
4.4 Lenguajes y gramáticas.
4.5Autómatas de estado finito no determinista.
4.6 Relación entre lenguajes y autómatas.

Unidad IV: LENGUAJES Y AUTÓMATAS.

4.1 INTRODUCCION A LENGUAJES Y AUTOMATAS
CONCEPTOS Y DEFINICIONES

Veamos algunos conceptos que nos permitirán conceptualizar la gramática

SÍMBOLO

Es una entidad abstracta, que no se va a definir. Normalmente los símbolos son letras (a,b,c,…z), dígitos (0,1,2…9) yotros caracteres (+,*,/,-,?...).

Un símbolo también puede estar formado por varias letras o caracteres, como las palabras reservadas de un lenguajede programación son símbolos de dicho lenguaje. Ejemplo:

-   a,b,c,#,+,-,*, then, begin, end, else, …

VOCABULARIO O ALFABETO

Un vocabulario o alfabeto es un conjunto finito de símbolos, no vacío. Para definir que un símbolo a pertenece a unalfabeto V, se utiliza la siguiente notación aÃŽV.

Los alfabetos se definen por enumeración de los símbolos que contienen, podemos ver los siguientes ejemplos:

V1= {A,B,C,D,E,F,…..,X,Y,Z}

V2= {a,b,c,d,0,1,2,3,4,*,#,+}

V3= {0,1}

V4= {if, then, begin, end, else, a,b,;,=,>}

También se pueden definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.

CADENAUna cadena es una secuencia finita de símbolos de un determinado alfabeto.

Ejm. Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:

abcb es una cadena del alfabeto V2

a+2*b es una cadena del alfabeto V2

000111 es una cadena del alfabeto V3

If a>b then b=a; es una cadena del alfabeto V4

LONGITUD DE CADENA

La longitud de una cadenaconsiste en el número de símbolos pertenecientes a la cadena. Ejm. Tomando en cuenta los ejemplos de cadena podemos decir que:

·   |abcb| es de longitud 4

·   |a + 2*b| es de longitud  5

·   |000111| es de longitud  6

·   |if a>b then a=b;| es de longitud  9

CONCATENACIÓN DE CADENAS

Sean A y B dos cadenas cualesquiera, se denomina concatenación de A y B a una nueva cadena AB constituidapor los símbolos de la cadena A seguidos por los de la cadena B.

El elemento neutro de la concatenación es l:

A l =  lA = A

UNIVERSO DEL DISCURSO

El conjunto de todas las cadenas que se pueden formar con los símbolos de un alfabeto, se denomina universo del discurso V y se representa por W(V). Evidentemente W(V) es un conjunto infinito. La cadena vacía pertenece a W(V).Ejm:

Sea unalfabeto con una sola letra V={a}, entonces el universo del discurso es:

W(V) = {l, a, aa, aaa, aaaa, ….}

que contiene infinitas cadenas.

GRAMÁTICA

Veamos algunos conceptos que nos ayuden a formular el concepto de gramática:

(Del lat. grammatĭca, y este del gr. γραμματική). f. Ciencia que estudia los elementos de una lengua y sus combinaciones. Artede hablar y escribir correctamenteuna lengua. Estudio de una lengua regido por el principio de que todos sus elementos mantienen entre sí relaciones sistemáticas. La que trata de formular una serie de reglas capaces de generar o producir todas las oraciones posibles y aceptables de un idioma o lenguaje

Una definición un tanto técnica: " La gramática es un ente formal para especificar, de una manera finita, el conjunto decadenas de símbolos que constituyen un lenguaje" . La gramática genera o describe un lenguaje.

AUTÓMATA

(Del latin. automăta, t. f. de -tus,y este del gr. αὐτόματος, espontáneo). m.Instrumento o aparato que encierra dentro de sí el mecanismo que le imprime determinados movimientos o respuestas. Máquina que imita la figura y los movimientos de un ser animado.

En el caso de los Procesadores de...