Produção (ciência da computação)
De Wikipedia, a enciclopédia encyclopedia
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 é disjunto de ; e um símbolo distinto , que é o inicial.
Este artigo não cita fontes confiáveis. (Dezembro de 2013) |
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 operador Kleene plus, é o operador Kleene estrela e 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: