viernes, 24 de febrero de 2012

Lenguajes y Gramáticas



Uno de los principales temas sobre los que trata la teoría de autómatas son las gramáticas y los lenguajes formales.

Cuando se habla de una gramática nos referimos al conjunto de reglas con las que se puede generar todas las posibilidades combinatorias de ese lenguaje. Además existen dos tipos de lenguajes, naturales y formales. En teoría de autómatas, se estudian principalmente los lenguajes formales y su utilidad computacional, en los cuales se utilizan las reglas combinatorias de estilo matemático.

Es importante saber hasta dónde puede llegar un lenguaje. Un alfabeto será siempre finito, esto significa que es un conjunto de símbolos finito con el cual se forman palabras. Las palabras son también finitas, pero el lenguaje puede tener un número infinito de palabras.

Ahora pongamos por ejemplo un alfabeto formado por dos caracteres {a, b}. Podemos crear combinaciones como aab, aba, abba entre otras, pero si definimos un lenguaje en el que el número de símbolos "a" deba ser mayor que el número de símbolos "b", abba ya no sería una sentencia válida para ese lenguaje.

Otro aspecto importante de los lenguajes es la palabra vacía, denominada como λ, la cual representa una cadena de longitud 0.

En cuanto a las gramáticas, se las representa como (V, Σ, p, S), donde:
- V es un conjunto finito de símbolos no-terminales.
- Σ es el alfabeto ó conjunto de símbolos terminales.
- P es una relación en (V υ Σ)* son las reglas de producción tal que los primeros elementos en p contienen al menos un símbolo es V.
- S € V es el símbolo de comienzo.

Además existen 4 tipos de gramáticas, ordenados según la Jerarquía de Chomsky.
- Gramática tipo 0: sin restricciones. Generan todos los lenguajes capaces de ser reconocidos por una Máquina de Turing.
- Gramática tipo 1: gramáticas sensibles al contexto. Se reconocen por un autómata linealmente acotado.
- Gramática tipo 2: gramáticas libres del contexto. Reconocidos por autómatas a pila.
- Gramática tipo 3: gramáticas regulares. Son los lenguajes aceptados por los autómatas finitos.

Una gramática formal está en Forma normal de Chomsky (FNC) si todas sus reglas de producción son de alguna de las siguientes formas:

A→BCo
A→αo

donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

También se puede dar como:

A→BCo
A→αo
S→ε

donde S es el símbolo distinguido (o inicial) de la gramática, A es un símbolo noterminal (o variable), B y C también son símbolos no terminales pero distintos de S , α es un símbolo terminal, y ε es la cadena nula (o vacía).

Como último apunte, se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG) si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un símbolo terminal.

Formalmente,cualquiera de las reglas tendrá la estructura:

A→aw

Donde "A" es el antecedente de la regla, que en el caso de las GIC debe ser necesariamente un solo smbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal":

A→a

Existe un teorema que prueba que cualquier GIC, cuyo lenguaje no contiene la palabra vacía, si no lo está ya, se puede transformar en otra equivalente que sí esté en FNG.


Referencias:
Lenguajes y Gramáticas

No hay comentarios:

Publicar un comentario en la entrada