¿Cómo puedo demostrar que Chomsky derivaciones en forma normal requieren 2n - 1 pasos?

Question

estoy tratando de probar lo siguiente:

Si G es un contexto libre de gramática en la forma normal de Chomsky, entonces para cualquier cadena w pertenece L (G) de longitud n ≥ 1, se requiere exactamente 2n -1 pasos para hacer cualquier derivación de w.

¿Cómo podría probar esto?

Answer 1

como una sugerencia - desde todas las producciones en Chomsky Forma Normal o bien tiene la forma

S → AB, para no terminales A y B, o la forma

S → x, para el terminal x,

Entonces derivar una cadena funcionaría de la siguiente manera:

• crear una cadena de exactamente n no terminales, a continuación,
• expandir cada no terminal a un solo terminal.

Aplicación de las producciones de la primera forma aumentarán el número de no terminales desde k hasta k + 1, ya que se reemplaza uno no terminal (-1) con dos no terminales (+2) para una ganancia neta de +1 no terminal. Desde su inicio con un no terminal, esto significa que debe hacer n - 1 producciones de la primera forma. A continuación, deberá n más de la segunda forma para convertir los no terminales a los terminales, dando un total de n + (n - 1) = 2n - 1 producciones.

Para demostrar que necesita exactamente esta cantidad, le sugiero que haga una prueba por contradicción y demuestre que no puede hacerlo con más o menos. Como sugerencia, trate de contar el número de producciones de cada tipo que se hacen y que muestra que si no es 2n - 1, o bien la cadena es demasiado corto, o todavía tendrá no terminales restantes.

Espero que esto ayude!