Linguagem livre de contexto determinística
 | Este artigo não cita fontes confiáveis. (Abril de 2013) |
 | Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Abril de 2013) |
Na teoria da linguagem formal, linguagens livres de contexto determinísticas (LLCD) são um subconjunto de linguagens livres de contexto (LLC). Elas são as linguagens livres de contexto que podem ser aceitos por um autômato determinístico (AD).
Descrição
[editar | editar código-fonte]A noção de LLCD está intimamente relacionado com o autômato com pilha determinístico (APD). É onde o poder linguagem de um autômato com pilha é reduzido se tornando determinístico. O autômato torna-se incapaz de escolher entre diferentes alternativas de transição de estado e, como conseqüência não pode reconhecer todas as linguagens livres de contexto. Gramáticas ambíguas nem sempre podem gerar um LLCD. Por exemplo, a linguagem dos palíndromos de mesmo comprimento no alfabeto de 0 e 1 tem a gramática ambígua livre de contexto S → 0S0 | 1S1 | ε. Uma seqüência arbitrária dessa linguagem não pode ser analisada sem ler todos os seu caracteres, o que significa que um autômato com pilha tem que tentar transições de estado alternativas para acomodar os diferentes comprimentos possíveis de uma cadeia semi-analisada.
Propriedades
[editar | editar código-fonte]Linguagens livres de contexto determinísticas podem ser reconhecidas por uma máquina de Turing determinística em tempo polinomial e O(log² n) e são um subconjunto da complexidade classe SC. O conjunto de LLCD não é fechado sob união, mas é fechada sob complemento.
Importância
[editar | editar código-fonte]As linguagens desta classe têm grande importância prática em ciência da computação como eles podem ser analisados muito mais eficientemente do que linguagens livres de contexto não determinísticas. A complexidade do programa e o tempo de execução de um autômato com pilha é muito menor do que a de um não-determinístico. Numa implementação ingênua, este último deve fazer cópias da pilha a cada passo de que um não-determinístico ocorre. O melhor algoritmo conhecido para testar a associação em qualquer linguagem livre de contexto é o algoritmo de Valiant, tendo O (n2.378), onde n é o comprimento da cadeia. Por outro lado, linguagens livres de contexto determinísticas podem, ser aceita em tempo O (n) por um (k) analisador sintático LR. Isto é muito importante para a tradução linguagem de programação, porque muitas linguagens pertencem a esta classe de linguagens.