Encerramentos e Contexto gramáticas livres

Question

Eu estou olhando por cima do meu currículo para a minha aula teórica ciência da computação e dentro da rubrica de Contexto gratuito Gramáticas ele lista "Propriedades de fechamento". Eu olhei através do meu livro sobre este assunto e achei muito pouco. O pouco que tem é um pouco acima da minha cabeça no momento (eu não ter tomado a ainda claro), mas eu entendo um pouco.

Eu queria saber se essa idéia de encerramentos dentro de gramática livre de contexto é o mesmo ou relacionado com a idéia de encerramentos dentro de programação funcional. Ele fala sobre combinando gramáticas e resolver sobreposições, tanto quanto eu posso dizer. Há um monte de peças para a seção dentro do livro que eu não entendo ainda, então eu não tenho certeza sobre se essas idéias são as mesmas.

(A pouco mais de contexto: Eu estou escrevendo um e-mail para o professor perguntando se o curso pode ser comutada para Ruby ou Python de Perl Se estes conceitos estão relacionados, que poderia ser outra razão que devemos usar Ruby sobre Perl.. )

Answer 1

O termo "fechamento" é usado um uma variedade de maneiras, a maioria de rastreamento de volta para um conceito matemático de conclusão, em algum sentido.

• Um operador é "fechou-se sobre" um conjunto de valores se aplicar esse operador para valores a partir do conjunto sempre produz um valor a partir do conjunto dado. Por exemplo, a adição é fechada sobre os inteiros, mas não divisão é (4/2 é integral, mas 5/2 não é). Assim, além de inteiros é de alguma forma "completa" no sentido de que a divisão não é.

• O "transitivo" fechamento de uma relação "completa" a relação, seguindo (todos os possíveis) múltiplas aplicações. Em termos diários, o conceito de "é um descendente do" é o fechamento transitivo da relação "é um filho de".

• Um "fecho" funcional é "completada" por exemplo especificando como as variáveis ??livres são para ser resolvido. Na expressão pseudo-código:

  bump = function(x) (x + y)
  

  x é o argumento para bump, mas a definição parece deixar "aberto" a questão de resolver y. Por outro lado, se definirmos:

  bumper = function(y) (function(x) (x + y))
  

  , em seguida, invocando bumper retorna uma função que adiciona o argumento original de bumper à argumentação da função criada, de modo que:

  add3 = bumper(3)
  

  é equivalente a definição:

  add3 = function(x) (x + 3)
  

  A definição aninhada é "fechado over" (ou concluída até) as variáveis ??disponíveis no ponto de sua definição.

Assim, com efeito, os usos de "fechamento" acima de tudo, têm diferentes significados específicos, e à primeira vista parecem alheios, mas não há uma relação subjacente sutil.

Answer 2

A propriedade de encerramento é assim: se L e M são linguagens livres de contexto, então é assim L | M. fechamentos de função são uma forma de implementar funções de primeira classe. Então, não, eles têm praticamente nada a ver uns com os outros.

Por que o mesmo nome, então? Um fechamento de função é 'fechado sobre' suas variáveis ??livres:

def adder(n): return lambda m: n + m

Aqui n é uma variável livre do lambda. O nome enfatiza isso porque Lisp originalmente não variáveis ??apertada sobre livres -. Eles tiram o seu valor a partir de qualquer ligação foi na pilha quando a função interna foi chamado

O encerramento de imóveis em matemática é um pouco mais óbvia: se um conjunto é fechado sob uma operação, em seguida, aplicar essa operação dentro desse conjunto não vai levá-lo de fora. Se você adicionar números inteiros, o que você ganha ainda é um número inteiro.

Answer 3

Darius está correta; "Propriedades de fechamento" não tem nada a ver com "fechamentos de função". Existem apenas tantas palavras para ir ao redor: - (

A idéia de propriedades de fechamento é aplicada toda ciência da computação acabou, mas ele é aplicado muito para diferentes classes de idiomas. As diferentes classes de línguas são importantes porque você precisa de uma tecnologia diferente para digitalizar ou reconhecer um enunciado. Por exemplo, as expressões regulares pode dizer se você tem uma palavra reservada, mas eles não podem dizer se você tem uma expressão com parênteses equilibrados --- para que você precisa de uma gramática livre de contexto.

As pessoas estão geralmente interessados ??em saber se se você tomar um langauge particular e você interseção ou união com outra língua, ou simplesmente complementar o idioma, você começa uma outra língua na mesma classe. Por exemplo, é possível escrever uma expressão regular que corresponde exatamente esses tokens que são não palavras reservadas? Podemos responder um sonoro "sim" porque linguagens regulares são fechados sob complemento, ou seja, o complemento de uma linguagem regular é em si uma linguagem regular. Este é um exemplo de uma propriedade de encerramento. Normalmente, a prova é construtiva, isto é, não só dizer-lhe que há existe uma expressão regular que descreve todos os tokens que não são reservados palavras, a prova da propriedade de encerramento irá dizer-lhe como find uma expressão tão regular.