Построить грамматику над {a, b}, чей язык

• Вам нужен базовый случай. Поскольку n может быть нулем, & epsilon; (пустая строка) на языке. Так что это должно сказать вам, с чего начать.

• Вы, кажется, думаете, что есть больше b с, чем a с. Но число b с ( n ) меньше или равно числу a с ( м ). Не может быть больше b с. Вместо добавления одного или двух b для каждого a, вам нужно добавить один или два a для каждого b. (Но см. Ниже.)

• Вы обрабатываете только те случаи, когда дополнительный a сопряжен с одним или двумя b с, которые, как упоминалось выше, должны быть обращены так дополнительный b в паре с некоторыми a с. Но в описании языка говорится m & le; 3 * n *, а не m & le; 2 * n *; дополнительный b может быть в паре с тремя a с.

Я считаю полезным начать с самых коротких строк в языке, а затем попытаться обобщить их. Какая самая короткая строка в этом языке? Мы можем выбрать n = 0 и m = 0, поскольку 0 < = 0 < = 0 < = 3x0, поэтому пустая строка находится на нашем языке. Поскольку пустая строка в языке, у нас должна быть продукция в нашей грамматике, подобная 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 < = 3n - но есть строки, которые эта продукция сама по себе пропускает. В таких случаях производство в порядке и должно быть сохранено; однако, то, что мы пропустили некоторые строки, указывает, что нам нужно найти другие производства, чтобы покрыть те случаи.

Какие случаи мы пропустили? Мы пропустили случай, когда m строго больше n. В произведении, которое мы догадались, мы использовали одно и то же число a и b, поэтому мы получаем строки с одинаковым номером. Само собой разумеется, что если нам нужны строки с более чем a, чем b, то нам нужно иметь продукцию, которая вводит больше, чем b. По нашей гипотезе мы все еще требуем, чтобы мы ввели хотя бы один из обоих; и мы уже представили по одному с каждым. Следующее логическое произведение, которое нужно угадать, - S := aaSb. Какие строки мы можем генерировать сейчас? Если мы проигнорируем производство S := aSb, это новое производство позволяет нам генерировать строки вида (a^2n)(b^n) строк на нашем языке; но что происходит, когда мы рассматриваем все три произведения?

Рассмотрим строку (a^k)(b^n), где n < = k < = 2n. Если k = n, то мы можем использовать производство S := aSb n раз, чтобы получить строку; аналогично, если k = 2n, мы можем использовать производство S := aaSb n раз. Что если n < k < 2n? Предположим, что k = n + j, где 0 < j < п. В этом случае мы можем использовать произведение 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

Есть много других грамматик для этого языка, все правильные, и многие пришли к использованию совершенно других методов, чем этот. Не думайте о таких проблемах как о применении формулы для получения заранее определенного ответа. Думайте о таких проблемах как о проблемах программирования. Вам дают спецификацию, и пока ваши вещи работают, это то, что имеет значение.