Operación de un sistema recursivo

Para dar idea de la operación de un sistema recursivo se plantea el siguiente ejemplo que consta de un símbolo axiomático inicial y de dos reglas, de la siguiente manera:

Axioma inicial: S

R.1  S→ W

R.2  W→ W + W

Entonces, la flecha se interpreta como la instrucción de reemplazar el símbolo de la izquierda por la cadena de símbolos de la derecha. Al aplicar la primera regla (R.1) obtendremos la línea W; al aplicar la segunda regla obtendremos la línea W + W; al aplicar otra vez la segunda regla (sustituyendo un caso de W por la cadena W + W) obtendremos la cadena W + W + W.

Quedaría así:

1.      W ( al aplicar R.1  del ejemplo anterior)

2.      W +  W ( al aplicar R.2)

3.      W + W + W ( al reaplicar R.2  a la línea anterior);

4.      W + W + W + W (al reaplicar R.2 a la línea anterior)

Y así sucesivamente sin fin. En una palabra la aplicación continuada de estas dos reglas enumera o especifica (técnicamente se dice ‘’genera’) un conjunto infinito de cadenas de la forma W, WW,WWW,WWWW… (Prescindiendo de + como símbolo de concatenación).

Un elemento como S en este ejemplo se llama elemento recursivo debido a que las cadenas derivadas de él pueden, a su vez, contenerlo.

Es así, como se dice que la gramática tiene que ser un sistema de procesos recursivos capaz de generar o especificar todas las oraciones generadas. Además, es importante que aunque una frase no sea ‘’aceptable’’ no quiere decir que no es ‘’gramatical’’.

Por lo tanto, no solo fue Chomsky el primero en introducir este y otros modelos de gramática formales, sino también el primero en estudiar a fondo sus propiedades matemáticas.

Chomsky empezó por demostrar, en su importante artículo de 1956, que no hay autómata de estados finitos, por muchos estados que tenga, capaz de representar una lengua natural; que la gramática ahormacional, aunque con más alcance, resulta también resulta también inadecuada y que solo una gramática transformacional es capaz de generar la aproximación más parecida (por el momento) a una lengua humana.