Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 85

В правильной грамматике вышеупомянутого вопроса , какова длина деривации (количество шагов, начинающихся с S) для генерации строки a l b m с l ≠ m?
(А) макс (л, м) + 2
(B) l + m + 2
(С) l + m + 3
(D) max (л, м) + 3

Ответ: (А)
Объяснение:
Правильная грамматика последнего вопроса была (D), которая:

S -> AC|CB
C -> aCb|epsilon
A -> aA|a
B -> Bb|b

Теперь наиболее оптимальным и интуитивно понятным способом создания строки вида a l b m было бы сначала использовать производственное правило «C -> aCb | epsilon», чтобы получить как можно больше a и b, что будет min ( л, м). Чтобы получить остальную часть строки, мы могли бы просто использовать последние два правила производства соответственно. Формально получая строку общего формата a l b m из приведенной выше грамматики —

1.	  S -> AC 
2.          -> A(aCb) 
3.          -> .... 
4.          -> ....
5.          -> A(am C bm) 
6.          -> A(am bm) 
7.          -> aA(am bm) 
8.          -> .... 
9.          -> ....
10.         -> a(l-m-1)A(am bm) 
11.         -> al bm

Из вышеприведенного набора шагов деривации мы можем подсчитать общее количество шагов следующим образом:


Production 1 took 1 step       : 1                   [using S->AC]
Production 2-5 took steps      : min(l,m)            [using C->aCb] 
Production 6 took 1 step       : 1                   [using C->epsilon]
Production 7-11 took steps     : max(l,m)-min(l,m)   [using A -> aA|a or B -> Bb|b]
                        
               Total steps   : max(l,m) + 2     

Следовательно, ответ должен быть (A) : max (l, m) + 2

Это объяснение предоставлено Vineet Purswani.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2006 | Вопрос 85

0.00 (0%) 0 votes