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.

ÍNDICEUnidad 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 DEFINICIONESVeamos 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 delalfabeto 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 cadena...
tracking img