Как я могу доказать, что дифференцирование в нормальной форме Хомского требует 2n - 1 шагов?

Question

Я пытаюсь доказать следующее:

Если G является контекстно-свободной грамматикой в ​​нормальной форме Хомского, то для любой строки w принадлежит L(G) длины n ≥ 1, для любого вывода w требуется ровно 2n-1 шагов.

Как мне доказать это?

Answer 1

Как подсказка - так как каждое произведение в нормальной форме Хомского либо имеет вид

S → AB, для нетерминалов A и B или вида

S → x, для терминала x,

Тогда получение строки будет работать следующим образом:

• Создайте строку из ровно n нетерминалов, затем
• Разверните каждый нетерминал до одного терминала.

Применение продукций первой формы увеличит число нетерминалов с k до k + 1, поскольку вы заменяете один нетерминал (-1) на два нетерминала (+2) для чистого усиления +1 нетерминала. Поскольку вы начинаете с одного нетерминала, это означает, что вам нужно выполнить n - 1 произведений первой формы. Затем вам потребуется еще n второй формы для преобразования нетерминалов в терминалы, что дает в общей сложности n + (n - 1) = 2n - 1 произведений.

Чтобы показать, что вам нужно именно столько, я бы предложил сделать доказательство от противоречия и показать, что вы не можете сделать это больше или меньше. В качестве подсказки попробуйте подсчитать количество произведений каждого типа, которые сделаны, и показать, что если это не 2n - 1, либо строка слишком короткая, либо у вас останутся нетерминалы.

Надеюсь это поможет!