Linguagem algébrica determinística

Na ciência da computação teórica e na teoria da linguagem , uma linguagem algébrica determinística é uma linguagem algébrica reconhecida (por estados finais) por um autômato push-down determinístico . O interesse das linguagens determinísticas é que sua análise sintática seja feita em tempo linear no comprimento da palavra, enquanto em qualquer linguagem algébrica a complexidade é cúbica, ou em qualquer caso se reduz à complexidade do produto da matriz, portanto é em O ( n 2,37 ) onde n é o comprimento da palavra pelo algoritmo de Valiant . Qualquer linguagem algébrica determinística pode ser descrita por uma gramática LR (1) e vice-versa. Isso permite que sejam usados para aplicações práticas. Assim, a maioria das linguagens de programação são linguagens algébricas determinísticas.

Exemplos

A linguagem é determinística. ${\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \}}$
A linguagem , onde está uma letra diferente , e onde está o retorno de , é determinística. ${\ displaystyle \ {wcw ^ {r} \ mid w \ in \ {a, b \} ^ {*} \}}$ $vs$ $a, b$ $w ^ r$ $C$

Propriedades

A classe das linguagens algébricas determinísticas contém estritamente a classe das linguagens racionais e está estritamente incluída na classe das linguagens algébricas e mesmo nas linguagens algébricas inequívocas .

O contra-exemplo típico de linguagem algébrica não determinística é o conjunto de palíndromos .

A classe de linguagens algébricas determinísticas é fechada por complementares. Contudo:

não é fechado por intersecção (mesmo contra-exemplo do caso não determinístico);
não é fechado por sindicato (consequência do fechamento por complementar e sindicato);
não é fechado por concatenação;
não é fechado por espelho, por exemplo, é algébrico determinístico, mas não . $\ {ca ^ {n} b ^ {n} \} \ xícara \ {da ^ {{2n}} b ^ {n} \}$ $\ {b ^ {n} a ^ {n} c \} \ xícara \ {b ^ {n} a ^ {{2n}} d \}$

Exemplos de linguagens não determinísticas

A linguagem não é determinística. ${\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 0 \} \ cup \ {a ^ {n} b ^ {2n} \ mid n \ geq 0 \}}$
A linguagem não é determinística em um alfabeto com pelo menos duas letras. Este idioma é composto de palavras, a segunda metade das quais contém pelo menos uma ocorrência da letra . ${\ displaystyle \ {w \ mid w = uv, | u | = | v |, | v | _ {a} \ geq 1 \}}$ $no$
A linguagem dos palíndromos não é determinística.

O princípio de construção dessas linguagens é o mesmo: o autômato push-down deve tomar uma decisão sem conhecer a totalidade dos dados; no primeiro exemplo, ele deve antecipar se o número de b é igual ou duplo o número de a , no segundo exemplo, ele deve testar a presença da letra a na segunda metade sem saber se ela já está no segundo tempo.

Existe um lema de iteração especial para linguagens algébricas determinísticas que torna possível provar formalmente que uma linguagem não é determinística. A afirmação é bastante complicada. Uma variante igualmente complicada desse lema é fornecida por Sheng Yu.

Notas e referências

Wolper 2006 , Seção 4.4.4, p. 97 .
Harrison 1978 , Teorema 11.8.5 ..
Michael Harrison até mostra que essa linguagem não é a união de um número finito de linguagens determinísticas.
Harrison 1978 , Teorema 11.8.3.

Bibliografia

(pt) Michael A. Harrison , Introdução à Teoria da Linguagem Formal , Leitura, Mass., Addison-Wesley ,1978, 594 p. ( ISBN 0-201-02955-3 , OCLC 266962302 )
Pierre Wolper , Introdução à calculabilidade: cursos e exercícios corrigidos , Paris, Dunod ,2006, 3 e ed. , 224 p. ( ISBN 2-10-049981-5 ).
Sheng Yu , “ Um lema de bombeamento para linguagens livres de contexto determinísticas ”, Information Processing Letters , vol. 31, n o 1,1989, p. 47–51 ( DOI 10.1016 / 0020-0190 (89) 90108-7 )