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

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde dezembro de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

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 seqüê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 s, um conjunto finito (conhecido como um alfabeto)  \ Sigma de símbolos terminais s que é disjuntos de  N e um símbolo distinto  S \ in N , que é o símbolo inicial.

Em uma gramática irrestrita, a produção é da forma  u \to v , onde  u e  v são seqüências arbitrárias de terminais e não terminaiss 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 Kleene plus operador, {}^{*} é o Kleene estrela operador, e  \cup 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:

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

A geração de gramática[editar | editar código-fonte]

Para gerar uma seqüência na língua, começa com uma seqüê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 seqüência particular de opções legais tomadas durante este processo de reescrita produz uma seqüê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 escolher a regra se aplique a ele. Se escolhermos uma regra, podemos substituir S com aSb e obter a seqüência aSb. Se escolhermos uma regra novamente, substituir  S com aSb e obter a seqüência aaSbb. Este processo é repetido até que temos apenas a partir do alfabeto de símbolos (por exemplo, a e b). Se agora escolher a regra 2, substituímos S com ba e obter a seqüê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\}.

Ver também[editar | editar código-fonte]