PUERTA | PUERTA CS 2013 | Pregunta 65 – Part 5

¿Cuál es el número máximo de movimientos de reducción que puede tomar un analizador de abajo hacia arriba para una gramática sin producción de épsilon y unidad (es decir, del tipo A -> є y A -> a) para analizar una string con n fichas?
(A) n/2
(B) n-1
(C) 2n-1
(D) 2 ⁿ

Respuesta: (B)
Explicación: Dado en la pregunta, una gramática sin producción de épsilon y unidad (es decir, de tipo A -> є y A -> a).

Para obtener el máximo número de movimientos de reducción, debemos asegurarnos de que en cada forma de oración solo se reduzca una terminal. Dado que no hay producción de unidades, las últimas 2 fichas requerirán solo 1 movimiento.

Entonces, para reducir la string de entrada de n tokens, primero reduzca n-2 tokens usando n-2 movimientos de reducción y luego reduzca los últimos 2 tokens usando la producción que tiene . Así que el total de n-2+1 = n-1 Reduce los movimientos.

Supongamos que la string es abcd. ( n = 4 ).

Podemos escribir la gramática que acepta esta string de la siguiente manera:

S->aB
B->bC
C->cd 

La derivación más a la derecha para lo anterior es:

S -> aB ( Reduction 3 )
-> abC ( Reduction 2 )
-> abcd ( Reduction 1 )

Podemos ver aquí que ninguna producción es por unidad o épsilon. Por lo tanto, 3 reducciones aquí.

Podemos obtener un número menor de reducciones con alguna otra gramática que tampoco produce producciones de unidades o épsilon,

S->abA
A-> cd

La derivación más a la derecha para lo anterior como:

S -> abA ( Reduction 2 )
-> abcd ( Reduction 1 )

Por lo tanto 2 reducciones.

Pero lo que nos interesa es saber el número máximo de reducciones que procede de la 1ª gramática. Por lo tanto, un total de 3 reducciones como máximo, que es (n – 1) como n = 4 aquí.

Por lo tanto, la opción B.

Cuestionario de esta pregunta