Produção (ciência da computação)

A produção ou regra de produção em ciência da computação é uma regra de reescrita, especificando a substituição de símbolos que podem ser realizados de forma recursiva para gerar novas sequências de símbolos. Um conjunto finito de produções $P$ é o principal componente na especificação de uma gramática formal (especificamente uma gramática gerativa). Os outros componentes são um conjunto finito $N$ de símbolo não terminal, um conjunto finito (conhecido como um alfabeto) $\ Sigma$ de símbolos terminais s, que é disjunto de $N$; e um símbolo distinto $S\ inN$, que é o inicial.

Em uma gramática irrestrita, a produção é da forma $u\to v$, onde $u$ e $v$ são sequências arbitrárias de terminais e não terminais. Porém, $u$ não pode ser a string vazia. Se $v$ é a string vazia, esta é representada pelo símbolo $\epsilon$, ou $\lambda$ (em vez de deixar o lado direito em branco). Então, produções são da forma:

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

Onde ${}^{+}$ é o operador Kleene plus, ${}^{*}$ é o operador Kleene estrela e $\cup$ denota conjunto união.

Os outros tipos de gramática formal na hierarquia Chomsky impõem restrições adicionais sobre o que constitui uma produção. Notavelmente de gramática livre de contexto, o lado esquerdo de uma produção devem ser um único símbolo não-terminal. Então produções são da forma:

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

A geração de gramática

Para gerar uma sequência na língua, começa com uma sequência que consiste em apenas um único símbolo start, e, em seguida, aplica-se sucessivamente as regras (qualquer número de vezes, em qualquer ordem) para reescrever essa string. Isso interrompe quando recebemos uma string contendo apenas terminais. A linguagem consiste de todas as cadeias de caracteres que podem ser geradas desta maneira. Qualquer sequência particular de opções legais tomadas durante este processo de reescrita produz uma sequência específica na língua. Se existem várias maneiras diferentes de gerar essa única corda, então a gramática está a ser dito ambígua.

Por exemplo, suponha que o alfabeto é composto por $a$ e $b$, com o símbolo de início $S$, e nós temos as seguintes regras:

1. $S\rightarrow aSb$

2. $S\rightarrow ba$

Então vamos começar com $S$; e pode-se escolher a regra que se aplica a ele. Se escolhermos uma regra, podemos substituir $S$ por $aSb$, obtendo a sequência $aSb$. Se escolhermos uma regra novamente, substituiremos $S$ com $aSb$ e obteremos a sequência $aaSbb$. Este processo é repetido até que tenhamos apenas a partir do alfabeto de símbolos (por exemplo, $a$ e $b$). Se agora escolhermos a regra 2, substituímos $S$ com $ba$ e obtemos a sequência $aababb$; e está feito. Podemos escrever esta série de escolhas mais rapidamente, usando símbolos: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$. A linguagem da gramática é o conjunto de todas as cadeias que podem ser gerados usando este processo: $\{ba,abab,aababb,aaababbb,\dotsc \}$.