Вот рекурсивное определение этого языка:
- пустая строка на языке
- b на языке
- бб на языке
- если x на языке является строкой, то xa на языке
- если x является строкой в языке, то xab на языке
- если x является строкой в языке, то xabb на языке
- в языке нет ничего, кроме как по вышеуказанным правилам
Во-первых, давайте удостоверимся, что это определение верно. Нетрудно утверждать, что это определение определяет строки, которые должны быть на нашем целевом языке; никакая строка с подстрокой bbb не может удовлетворять вышеуказанным правилам. Охватывает ли определение все случаи, чтобы все строки без подстроки bbb работали? На самом деле, это должно. Рассмотрим любую строку в языке. Он либо имеет длину меньше трех (в этом случае мы можем проверить, что все возможные строки обрабатываются правильно, каковы они есть); для более длинных строк они должны заканчиваться на a, ab или abb (они не могут заканчиваться на bbb). Наши правила подразумевают существование строки x в языке без этих суффиксов, которые можно рекурсивно проверять на членство. Это можно изменить, чтобы получить убедительное доказательство математической индукцией.
Имея рекурсивное определение, подобное приведенному выше, мы можем просто записать соответствующую грамматику:
S -> e | b | bb | Sa | Sab | Sabb
Настоящей изобретательностью здесь было определение. Как я это сделал? Я подумал о самых коротких строках в языке - уникальных, которые не соответствуют шаблону - и затем спросил, как сделать более длинные строки из более коротких. То есть, учитывая строку в языке, как сделать ее больше? Это ключ к тому, что позволяют нам делать контекстно-свободные грамматики.