Conceptos basicos de lenguajes formales

Universidad Autónoma del Estado de[pic 1][pic 2][pic 3][pic 4][pic 5]

Hidalgo Instituto de Ciencias Básicas e Ingeniería

Área Académica de Computación y

Electrónica

Licenciatura en Sistemas Computacionales

Lenguajes y Autómatas

Docente: M. en C. Isaias Pérez Pérez

Tema:[pic 6][pic 7]

Conceptos Básicos de Lenguajes Formales

Resumen:

El presente documento aborda de manera

esencial los conceptos elementales de los lenguajes formales, nociones fundamentales para la comprensión de los diversos temas abordados   dentro   de   la   teoría   de   la

computación.

Palabras Clave:

Símbolo, cadena, alfabeto, lenguaje formal.

Tema:[pic 8][pic 9]

Conceptos Básicos de Lenguajes Formales

Abstract:

This paper addresses fundamental manner

the  basic  concepts  of  formal  languages, basic concepts for the understanding of the various  issues  addressed  in  the  theory  of

computation.

Keywords:

Symbol, string, alphabet, formal language.

Concepto de Símbolo

Es una entidad abstracta que no posee definición, de la misma manera que los conceptos de “punto” y “línea”, no se definen en geometría.

Las letras y los dígitos son ejemplos de símbolos usados con frecuencia [1].

Ejemplos:[pic 10][pic 11]

a, b, c,…, 1, 2, 3,…, #, $, %,…

Definición de Cadena

Es una secuencia finita de símbolos yuxtapuestos. Se utilizan las letras minúsculas del final del alfabeto (w, x, y, z), para designar a las cadenas [1], [2].

Ejemplos:[pic 12][pic 13]

w = abc

x = 321abc

y = #3a$%1, …

[pic 14][pic 15]

Longitud de Cadena

Se denota como |w|(donde w es una cadena) y se define como el número de símbolos que componen la cadena.

Ejemplos: Sean las cadenas w = abcd,  x = 0123a, entonces |w| = 4, |x| = 5

Caso especial: La cadena vacía (ϵ), es la cadena

que contiene cero símbolos (|ϵ| = 0) [1], [2].

[pic 16][pic 17]

Prefijos y Sufijos de Cadena

Los prefijos están formados por los primeros símbolos  de  la  cadena;  y  los  sufijos,  por  los últimos. Un prefijo o sufijo de una cadena que no sea la misma cadena es un prefijo o sufijo propios [1], [2].

Ejemplo: Sea la cadena w = abc; los prefijos y sufijos, son

Prefijos: ϵ, a, ab, abc.

...