Produção (informática) - Production (computer science)

A produção ou produção regra em ciência da computação é uma regra de reescrita especificar uma substituição símbolo que pode ser executada de forma recursiva para gerar novas sequências de símbolos. Um conjunto finito de produções é o principal componente na especificação de uma gramática formal (especificamente uma gramática generativa ). Os outros componentes são um conjunto finito de símbolos não terminais , um conjunto finito (conhecido como um alfabeto) de símbolos terminais que é separado a partir e um símbolo distinto que é o símbolo de início . ${\ Displaystyle P}$ ${\ N} displaystyle$ ${\ Displaystyle \ Sigma}$ ${\ N} displaystyle$ ${\ Displaystyle S \ em N}$

Em uma gramática sem restrições , uma produção é da forma onde e são sequências arbitrárias de terminais e não terminais no entanto não pode ser a cadeia vazia. Se for a cadeia vazia, este é indicado pelo símbolo , ou (em vez de deixar o espaço em branco do lado direito). Então produções são membros do produto cartesiano ${\ Displaystyle u \ a v}$ ${\ Displaystyle u}$ ${\ Displaystyle v}$ ${\ Displaystyle u}$ ${\ Displaystyle v}$ ${\ Displaystyle \ epsilon}$ ${\ Displaystyle \ lambda}$

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

,

onde é o vocabulário , é a estrela de Kleene operador, indica concatenação , e denota definir união . Se não permitir que o símbolo inicial para ocorrer em (a palavra no lado direito), temos de substituir por no lado direito do símbolo de produto cartesiano. ${\ Displaystyle V: = N \ chávena \ Sigma}$ ${\ Displaystyle {} ^ {*}}$ ${\ Displaystyle V ^ {*} NV ^ {*}}$ ${\ Displaystyle \} copo$ ${\ Displaystyle v}$ ${\ Displaystyle V ^ {*}}$ ${\ Displaystyle (V \ setminus \ {S \}) ^ {*}}$

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

{\ Displaystyle N \ a (N \ chávena \ Sigma) ^ {*}}

geração de gramática

Para gerar uma string na linguagem, começa-se com uma corda que consiste em apenas um único símbolo de início , em seguida, aplica-se sucessivamente as regras (qualquer número de vezes, em qualquer ordem) para reescrever essa string. Este pára quando obtemos uma string contendo somente terminais. A linguagem é composto por todas as cordas que podem ser geradas dessa maneira. Qualquer seqüência particular de opções legais tomadas durante este processo de reescrita produz uma string em particular na língua. Se existem várias maneiras diferentes de gerar essa única corda, então a gramática é dito ser ambígua .

Por exemplo, suponha o alfabeto consiste e , com o símbolo de início , e nós temos as seguintes regras: ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle S}$

1.

{\ Displaystyle S \ rightarrow ASB}

2.

{\ Displaystyle S \ rightarrow ba}

então vamos começar com , e pode escolher a regra se aplique a ele. Se escolhermos regra 1, substituir com e obter a cadeia . Se escolhermos regra 1 novamente, substituímos com e obter a cadeia . Este processo é repetido até que temos apenas símbolos de alfabeto (por exemplo, e ). Se nós agora escolher a regra 2, substituímos com e obter a cadeia , e está feito. Podemos escrever esta série de escolhas mais rapidamente, usando símbolos: . A linguagem da gramática é o conjunto de todas as cordas que podem ser gerados usando este processo: . ${\ Displaystyle S}$ ${\ Displaystyle S}$ ${\ Displaystyle ASB}$ ${\ Displaystyle ASB}$ ${\ Displaystyle S}$ ${\ Displaystyle ASB}$ ${\ Displaystyle aaSbb}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle S}$ ${\ Displaystyle ba}$ ${\ Displaystyle aababb}$ ${\ Displaystyle S \ Rightarrow ASB \ Rightarrow aaSbb \ Rightarrow aababb}$ ${\ Displaystyle \ {ba, abab, aababb, aaababbb, \ dotsc \}}$