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

Производственное , или производственное правило в информатике — это правило перезаписи определяющее замену символов, которая может выполняться рекурсивно для создания новых последовательностей символов. Конечный набор продукций $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 \}$ .