Производство (информатика)

Производственное определяющее или производственное правило в информатике — это правило перезаписи, замену символов, которая может выполняться рекурсивно для создания новых последовательностей символов. Конечный набор продукций $P$ является основным компонентом спецификации формальной грамматики (в частности, порождающей грамматики ). Остальные компоненты представляют собой конечное множество $N$ , нетерминальных символов конечное множество (известное как алфавит) $\Sigma$ терминальных символов , не пересекающихся с $N$ и выдающийся символ $S\in N$ это стартовый символ .

В неограниченной грамматике продукция имеет вид $u\to v$ , где $u$ и $v$ являются произвольными строками терминалов и нетерминалов, и $u$ не может быть пустой строкой . Если $v$ пустая строка, она обозначается символом $\epsilon$ , или $\lambda$ (вместо того, чтобы оставлять правую часть пустой). Таким образом, произведения являются членами декартова произведения.

V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}

,

где $V:=N\cup \Sigma$ это словарный запас , ${}^{*}$ является звездным оператором Клини , $V^{*}NV^{*}$ указывает на конкатенацию , $\cup$ обозначает объединение множеств , а $\setminus$ обозначает набор минус или набор разностей . Если мы не разрешим появление стартового символа в $v$ (слово справа), нам нужно заменить $V^{*}$ к $(V\setminus \{S\})^{*}$ справа от декартового символа произведения. ^[1]

Другие типы формальной грамматики в иерархии Хомского накладывают дополнительные ограничения на то, что представляет собой производство. В частности, в контекстно-свободной грамматике левая часть продукции должна быть одним нетерминальным символом. Итак, произведения имеют вид:

N\to (N\cup \Sigma )^{*}

Генерация грамматики

Чтобы сгенерировать строку в языке, нужно начать со строки, состоящей только из одного начального символа , а затем последовательно применять правила (любое количество раз и в любом порядке) для перезаписи этой строки. Это прекращается, когда получается строка, содержащая только терминалы. Язык состоит из всех строк, которые можно сгенерировать таким образом. Любая конкретная последовательность допустимых вариантов выбора, предпринятая в ходе этого процесса переписывания, дает в языке одну конкретную строку. Если существует несколько разных способов генерации этой единственной строки, то грамматика называется неоднозначной .

Например, предположим, что алфавит состоит из $a$ и $b$ , с начальным символом $S$ , и у нас есть следующие правила:

1.

S\rightarrow aSb

2.

S\rightarrow ba

тогда мы начнем с $S$ и может выбрать правило, которое будет применяться к нему. Если мы выберем правило 1, мы заменим $S$ с $aSb$ и получить строку $aSb$ . Если мы снова выберем правило 1, мы заменим $S$ с $aSb$ и получить строку $aaSbb$ . Этот процесс повторяется до тех пор, пока у нас не останутся только символы алфавита (т. е. $a$ и $b$ ). Если мы теперь выберем правило 2, мы заменим $S$ с $ba$ и получить строку $aababb$ , и готово. Мы можем записать эту серию выборов более кратко, используя символы: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$ . Язык грамматики — это набор всех строк, которые могут быть сгенерированы с помощью этого процесса: $\{ba,abab,aababb,aaababbb,\dotsc \}$ .