Формальные грамматики. Пример

Рассмотрим формальную грамматику, которая в какой-то степени напоминает фрагмент грамматики русского языка и задает формальный язык, состоящий из четырех русских предложений. В этой формальной грамматике используются элементы, играющие роль членов предложения или частей речи:

<предложение>

<подлежащее>

<сказуемое>

<дополнение>

<прилагательное>

<существительное>

Эти элементы заключены в угловые скобки, чтобы отличать их от слов из фактического словаря, составляющих предложения языка. В нашем примере словарь состоит из следующих пяти слов, или «символов»: V= {дом, дуб, заслоняет, старый, (точка)}. В грамматике имеются определенные правила, содержащие информацию о том, как их этих символов можно строить предложения языка. Одно из этих правил таково:

1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.

Это правило интерпретируется следующим образом: «Предложение может состоять из подлежащего, за которым следует сказуемое, затем дополнение и точка». В грамматике вполне могут быть и другие правила, задающие предложения другой структуры. Однако в данной грамматике таких правил нет. Остальные правила таковы:

2. <подлежащее> ® <прилагательное> <существительное>

3. <дополнение> ® <прилагательное> <существительное>

4. <сказуемое> ® заслоняет

5. <прилагательное> ® старый

6. <существительное> ® дом

7. <существительное> ® дуб

Применим эту грамматику для порождения (или вывода) предложения.

По правилу 1 предложение имеет вид:

<предложение> ¹® < подлежаще е> <сказуемое> <дополнение>²→

²→ <прилагательное><существительное> <сказуемое>< дополнение > ³→

³→ < прилагательно е><существительное> <сказуемое> <прилагательное> <существительное> ⁴→Старый <существительное> <сказуемое> < прилагательно е> <существительное>

⁴ → Старый <существительное > <сказуемое> старый <существительное >

^6,7→Старый дом <сказуемое> старыйдуб

⁴ → Старый домзаслоняетстарыйдуб

Таким образом, получаем готовое предложение:

Старый дом заслоняет старый дуб.

Этот вывод можно наглядно изобразить в виде дерева. Дерево вывода показывает, какие правила применялись к различным промежуточным элементам, но скрывает порядок их применения. Таким образом, можно видеть, что результирующая цепочка не зависит от порядка, в котором делались замены промежуточных элементов. Говорят, что дерево представляет собой «синтаксическую структуру» предложения.

Идея вывода показывает другие интерпретации правил, подобных правилу <подлежащее> ® <прилагательное> <существительное>. Вместо того, чтобы говорить «подлежащее это прилагательное, за которым следует существительное», можно сказать, что подлежащее «порождает» (или «из него выводятся», или «его можно заменить на») < прилагательное> <существительное>.

С помощью приведенной выше грамматики можно вывести также три других предложения, а именно:

Старый дуб заслоняет старый дом.

Старый дом заслоняет старый дом.

Старый дуб заслоняет старый дуб.

Эти предложения и предложение, выведенное раньше, и есть все предложения порождаемые данной грамматикой.

Множество, состоящее из этих четырех предложений, называется языком, который определяется данной грамматикой («порождается ею» или «выводится в ней»).