Linguagem livre de contexto determinística - Deterministic context-free language

Em teoria linguagem formal , linguagens livres de contexto determinísticos ( DCFL ) são um subconjunto próprio de linguagens livres de contexto . Elas são as linguagens livres de contexto que podem ser aceitas por um autômato pushdown determinístico . Os DCFLs são sempre inequívocos, o que significa que admitem uma gramática inequívoca . Existem CFLs não determinísticos e não ambíguos, portanto, os DCFLs formam um subconjunto adequado de CFLs não ambíguos.

Os DCFLs são de grande interesse prático, pois podem ser analisados ​​em tempo linear, e várias formas restritas de DCFGs admitem analisadores práticos simples. Eles são, portanto, amplamente usados ​​na ciência da computação.

Descrição

A noção de DCFL está intimamente relacionada ao autômato pushdown determinístico (DPDA). É onde o poder da linguagem dos autômatos pushdown é reduzido se os tornarmos determinísticos; os autômatos pushdown tornam-se incapazes de escolher entre diferentes alternativas de transição de estado e, como consequência, não podem reconhecer todas as linguagens livres de contexto. Gramáticas inequívocas nem sempre geram um DCFL. Por exemplo, a linguagem de palíndromos de comprimento par no alfabeto de 0 e 1 tem a gramática livre de contexto não ambígua S → 0S0 | 1S1 | ε. Uma string arbitrária desta linguagem não pode ser analisada sem ler todas as suas letras primeiro, o que significa que um autômato pushdown tem que tentar transições de estado alternativas para acomodar os diferentes comprimentos possíveis de uma string semi-analisada.

Propriedades

Linguagens livres de contexto determinísticas podem ser reconhecidas por uma máquina de Turing determinística em tempo polinomial e espaço O (log ² n ); como corolário, DCFL é um subconjunto da classe de complexidade SC .

O conjunto de linguagens livres de contexto determinísticas é encerrado nas seguintes operações:

• complemento
• homomorfismo inverso
• quociente certo com uma linguagem regular
• pre: pre ( ) é o subconjunto de todas as strings com um prefixo adequado ao qual também pertence .${\ displaystyle L}$${\ displaystyle L}$
• min: min ( ) é o subconjunto de todas as strings que não possuem um prefixo adequado em .${\ displaystyle L}$${\ displaystyle L}$
• max: max ( ) é o subconjunto de todas as strings que não são o prefixo de uma string mais longa em .${\ displaystyle L}$${\ displaystyle L}$

O conjunto de linguagem livre de contexto determinística não é fechado nas seguintes operações:

• União
• interseção
• concatenação
• Estrela de Kleene
• morfismo ε-free
• Imagem espelhada

Importância

As linguagens desta classe têm grande importância prática na ciência da computação, pois podem ser analisadas com muito mais eficiência do que as linguagens livres de contexto não determinísticas. A complexidade do programa e do tempo de execução de um autômato pushdown determinístico é muito menor do que a de um não-determinístico. Na implementação ingênua, o último deve fazer cópias da pilha sempre que ocorrer uma etapa não determinística. O algoritmo mais conhecido para testar a associação em qualquer linguagem livre de contexto é o algoritmo da Valiant , levando tempo O ( n ^2,378 ), onde n é o comprimento da string. Por outro lado, linguagens livres de contexto determinísticas podem ser aceitas em tempo O ( n ) por um analisador LR ( k ) . Isso é muito importante para a tradução de linguagem de computador porque muitas linguagens de computador pertencem a essa classe de linguagens.

Veja também

• Linguagem livre de contexto
• Autômato pushdown determinístico
• Gramática livre de contexto determinística
• Linguagem simples determinística

Referências