Lenguajes formales

3.1 CONCEPTOS BÁSICOS DE GRAMÁTICAS
1. Ingeniera en Informática
1.1 Teoría de la computación

Una gramática es una estructura G=(V,T, P, s0) donde
[pic]

Una pareja [pic]se escribe como [pic], o bien [pic]. Se dice que [pic]es el antecedente de la regla y que [pic]es su consecuente. Si [pic]es un conjunto de reglas con un antecedente común, se simplifica la notación y se escribe [pic]oalternativamente [pic]Dadas dos palabras [pic]decimos que [pic]se sigue de [pic]en G, y escribimos [pic], o simplemente [pic], cuando [pic]resulte de [pic]al intercambiar una partícula de [pic], que sea el antecedente de una regla, por el respectivo consecuente de la regla.

En símbolos,
| [pic]|(3)|

Decimos que [pic]se deriva de [pic]en G, y escribimos [pic], o simplemente [pic], si existe una sucesión finita de palabras, cuyos primero y último elementos coinciden con [pic]y [pic]respectivamente, y cualquier elemento en la sucesión se sigue del anterior. En símbolos,
| [pic]|(4)|

En tal caso, la sucesión de palabras y producciones[pic], donde [pic]se sigue de [pic]precisamente por la aplicación de la producción Pi, es una derivación de [pic]a partir de [pic]. Así pues, la relación ``se_deriva'' es la cerradura reflexivo-transitiva de la relación ``se_sigue'' El lenguaje de la gramática es el conjunto de palabras formadas con símbolos terminales que se derivan delsímbolo inicial,
[pic]

3.2 JERARQUÍA DE CHOMSKY
1. Ingeniera en Informática
1.1 Teoría de la computación

En 1959 Noam Chomsky clasifico las gramáticas en cuatro familias. Las gramáticas no restringidas, sensibles al contexto, independientes del contexto y las gramáticas regulares que se conocen como gramáticas de tipo cero, uno, dos y tres respectivamente. Los lenguajes que resultan dedichas gramáticas también se identifican con lenguajes de tipo cero, uno, dos y tres. A esta jerarquía de lenguaje se le conoce como la jerarquía de chomsky.

|GRAMATICA |TIPO |LENGUAJE QUE GENERA |
|Regular |3 |Lenguaje tipo 3 o lenguaje regular |
|Independiente del contexto |2 |Lenguajede tipo 2 o lenguaje independiente al contexto|
|Sencible al contexto |1 |Lenguaje tipo 1 lenguaje sensible al contexto. |
|Tipo no restringido |0 |Tipo cero lenguaje no restringido. |

3.4 GRAMÁTICA REGULAR
1. Ingeniera en Informática
1.1 Teoría de la computación
Es aquella gramática cuyas reglas de reescritura tienen las siguientesrestricciones:
1.- El lado izquierdo de cualquier regla de reescritura debe consistir en un solo no terminal, el lado derecho debe ser un terminal seguido por un no terminal, o un solo terminal o la cadena vacía
Ejemplo:
|Z [pic]yX |
|X[pic]y |
|X[pic][pic] |

Las siguientes regla de reescritura no estarían permitidas en una gramática regular.
Ejemplo:
|yW[pic]X ||X [pic]xZy |
|YX[pic]WvZ |

En una gramática regular cualquier regla de la forma N[pic]x podría remplazarse con el par de reglas siguientes:
|N[pic]xX |
|X[pic][pic]|

Donde X es un no terminal que no aparece en ningún otro lugar de la gramática, sin alterar el conjunto de cadenas que podría generar la gramática.
N [pic]xX [pic]x[pic] = x
La importancia de lasgramáticas regulares reside en que los lenguajes generados por ellas son exactamente aquellos que reconocen los autómatas finitos.
NOTA:
[pic]se interpreta como "puede ser", "se compone de", "es sustituida por".
\ se interpreta como "o" ejemplo: E[pic]A y E[pic]B se unen en E[pic]A\B.
[pic]se interpreta como "derivar", "produce" o "genera".

3.3 GRAMÁTICAS LIBRES DEL CONTEXTO
1. Ingeniera en...