Я считаю полезным начать с самых коротких строк в языке, а затем попытаться обобщить их.Какая самая короткая строка в этом языке?Мы можем выбрать n = 0 и m = 0, так как 0 <= 0 <= 0 <= 3x0, поэтому на нашем языке пустая строка.Поскольку в языке есть пустая строка, в нашей грамматике должна быть продукция, подобная <code>S := e.
Теперь, как нам получить более длинные строки в языке?Мы могли бы добавить несколько производств только для добавления a к нашим строкам или просто для добавления b;однако такие правила не могут быть использованы для расширения нашего базового случая (S := e), поскольку добавление только или только b к пустой строке не приведет к получению строки в языке.Эти произведения могут привести нас к цепочке на языке, но они не будут удерживать нас на таком пути очевидным или простым способом.Мы хотим, чтобы в нашей грамматике были простые произведения, поэтому мы можем быть уверены, что это правильно.
Альтернатива добавлению a и b по отдельности - это сложить их вместе.Обратите внимание, что когда у вас есть языки, в которых части строк зависят друг от друга, вы, как правило (всегда, за исключением явных, но не фактических зависимостей), обнаруживает, что произведения должны связывать эти зависимые части;в противном случае зависимость может быть «забыта» во время получения строки.Мы предполагаем, что наши произведения должны только когда-либо складывать a и b вместе и продолжать эту гипотезу.
Во-первых, мы можем догадаться, что произведение S := aSb должно быть включено в нашу грамматику.Почему мы можем догадаться об этом?Ну, исходя из нашей гипотезы, мы знаем, что нам нужно сложить a и b вместе, что мы и делаем здесь.Кроме того, поскольку мы хотим, чтобы правило генерировало строки общей длины, мы понимаем, что в производстве должен использоваться нетерминал, из которых у нас в настоящее время есть только один (напомним, что мы стремимся строить строки в нашем базовом случае, которыйпроизводится из S, поэтому использование этого нетерминала естественно).Наконец, мы знаем, что все a должны быть слева от всех b, и это единственный порядок трех символов, который генерирует строки в соответствии с этим шаблоном.
Какие строки позволяет нам генерировать это производство?Мы можем получить S := e, S := aSb := ab, S := aSb := aaSbb := aabb,…, S := … := (a^n)(b^n).Мы видим, что эти строки на языке - так как 0 <= n <= n <= 3n - но есть строки, которые эта продукция сама по себе пропускает.В таких случаях производство в порядке и должно быть сохранено;однако, то, что мы пропустили некоторые строки, указывает на то, что нам нужно найти другие производства, чтобы покрыть эти случаи. </p>
Какие случаи мы пропустили?Мы пропустили случай, когда m строго больше n.В произведении, которое мы догадались, мы использовали одно и то же число a и b, поэтому мы получаем строки с одинаковым номером.Само собой разумеется, что если мы хотим, чтобы строки имели больше a, чем b, то нам нужно иметь продукцию, которая вводит больше a, чем b.По нашей гипотезе мы все еще требуем, чтобы мы ввели хотя бы один из обоих;и мы уже представили по одному с каждым.Следующее логическое произведение, которое нужно угадать - S := aaSbКакие строки мы можем генерировать сейчас?Если мы игнорируем производство S := aSb, это новое производство позволяет нам генерировать строки вида (a^2n)(b^n) строк на нашем языке;но что происходит, когда мы рассматриваем все три произведения?
Рассмотрим строку (a^k)(b^n), где n <= k <= 2n.Если k = n, то мы можем использовать производство <code>S := aSb n раз, чтобы получить строку;аналогично, если k = 2n, мы можем использовать производство S := aaSb n раз.Что если n < k < 2n?Предположим, что k = n + j, где 0 S := aaSb ровно j раз, а производство S := aSb ровно n - j раз, чтобы получить 2j + n - j = n + j = k экземпляров a и n экземпляров b.Следовательно, эти три правила вместе позволяют нам генерировать все строки, где число a находится между числом b и двойным числом b, включительно на обоих концах.
Мы по-прежнему не можем генерировать строки, в которых число a больше чем вдвое больше числа b;однако, основываясь на наших вышеупомянутых успехах, мы можем угадать S := aaaSb и использовать аналогичные рассуждения, чтобы показать, что эти четыре произведения вместе дают нам именно тот язык, который мы намеревались генерировать.Грамматика, к которой мы пришли, выглядит следующим образом:
S := e
S := aSb
S := aaSb
S := aaaSb
Существует множество других грамматик для этого языка, все правильно, и многие пришли к использованию совершенно других методов, чем этот.Не думайте о таких проблемах как о применении формулы для получения заранее определенного ответа.Думайте о таких проблемах как о проблемах программирования.Вам дают спецификацию, и пока ваши вещи работают, вот что имеет значение.