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 é o principal componente na especificação de uma gramática formal (especificamente uma gramática gerativa). Os outros componentes são um conjunto finito de símbolo não terminal, um conjunto finito (conhecido como um alfabeto) de símbolos terminais s que é disjuntos de e um símbolo distinto , que é o símbolo inicial.

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

Onde é o Kleene plus operador, é o Kleene estrela operador, e denota conjunto união.

Os outros tipos de gramática formal na hierarquia Chomsky impor 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:

A geração de gramáticaEditar

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   e  , com o símbolo de início  , e nós temos as seguintes regras:

1.  
2.  

então vamos começar com  , e pode escolher a regra se aplique a ele. Se escolhermos uma regra, podemos substituir   com   e obter a sequência  . Se escolhermos uma regra novamente, substituir   com   e obter a sequência  . Este processo é repetido até que temos apenas a partir do alfabeto de símbolos (por exemplo,   e  ). Se agora escolher a regra 2, substituímos   com   e obter a sequência  , 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 cadeias que podem ser gerados usando este processo:  .

Ver tambémEditar