Info

• Boolean retrieval is a technique used in information retrieval to retrieve relevant documents based on a user's query.
• Les langages formels étudient divers ensembles de chaînes de caractères ayant des propriétés intéressantes du point de vue informatique.
• Un alphabet est un ensemble fini non vide d’éléments appelés des symboles (ou des lettres) de l’alphabet.
• Un mot sur un alphabet est une suite finie de lettres notée Σ⋆.
• Le mot vide, noté ε, est l’unique mot constitué de 0 lettre.
• La longueur d’un mot u sur un alphabet Σ est notée | u |.
• Si a ∈ Σ, le nombre d’occurrences de la lettre a dans u est noté | u | a.
• Sur Σ = { a, b, c }, l’ensemble des valeurs possibles pour un registre de calcul est l’ensemble { u ∈ Σ ⋆ | | u | = 64 } avec Σ = { 0 , 1 }.
• Cette grammaire est ambigüe car il y a deux arbres de dérivation possibles (qui correspondent à deux manières de parenthéser les if) :
• La grammaire de l’exemple 4.32 pour le langage de Dyck est non ambigüe.
• Le langage C et une version simplifiée d’une partie de sa grammaire sont : I → if ( E ) I I → if ( E ) I else I → E ; I |.
• Premier arbre if (x>4) { if (x<5) x = 12; else x = 42 ; }
• Cette grammaire permet d’obtenir : if (x>4) if (x<5) x=12; else x=42;.
• Second arbre if (x>4) { if (x<5) x = 12; } else x = 42 ;
• a ⋆ bc ⋆ est une expression régulière linéaire.
• ba ⋆ bc ⋆ b n’est pas une expression régulière linéaire.
• Si L 1 est un langage local, alors L ⋆ 1 est un langage local.
• Si r est une expression linéaire, alors L ( r ) est un langage local.
• Si L 1 et L 2 sont des langages locaux, alors L 1 ∩ L 2 est un langage local.
• Si L 1 est un langage local sur un alphabet Σ 1, L 2 est un langage local sur un alphabet Σ 2, et Σ 1 ∩ Σ 2 = ∅, alors : L 1 ∪ L 2 est un langage local sur Σ 1 ∪ Σ 2.
• Si v ∈ L(A), alors son chemin acceptant est de la forme qiε − → A q2i v − → ∗ A q2fε − → A qf.
• Si v ∈ L(r⋆1), alors son chemin acceptant est de la forme qiε − → A q1i v1 ··· vm − → ∗ A q1fε − → A qf.
• Si v ∈ L(r1 | r2), alors son chemin acceptant est de la forme qiε − → A q1i v − → ∗ A q1fε − → A qf.
• r = r⋆1 : notons A = th(r).
• Si v ∈ L(A), alors son chemin acceptant est de la forme qiε − → A q1i v1 ··· vm − → ∗ A q1fε − → A qf.
• Si v ∈ L(r⋆1), alors son chemin acceptant est de la forme qiε − → A q1i v − → ∗ A q1fε − → A qf.
• La concaténation de deux mots u et v sur un même alphabet Σ, de longueurs respectives n et m, est notée u · v (ou uv).
• L’opération de concaténation est une loi interne associative de Σ⋆, dont ε est l’élément neutre.
• L'automate obtenu est bien déterministe.
• L'automate reconnait les mêmes mots que l'automate A a 3.
• Si |u| = 0, alors R 0 = I.
• Un langage est reconnaissable par un automate fini déterministe si et seulement si c'est reconnu par un automate fini non déterministe.
• La longueur de l'automate déterminé est égale à la longueur de l'automate initial.
• Pour déterminiser une partie d'un automate fini non déterministe, il suffit de l'automate des parties.
• Si |u| = n + 1, alors R n = {q ∈ Q N | ∃ q i ∈ I, q i u −→∗ A N q}, et R n +1 = δ D (R n, a), qui est l'ensemble des états q tels que ∃ q i ∈ I, q i u −→∗ A N q.
• Pour un mot de taille n, si le chemin unique pour u depuis I dans l'automate initial est le même que le chemin unique pour u dans l'automate déterminé, alors R n = {q ∈ Q N | ∃ q i ∈ I, q i u −→∗ A N q}.
• Si L ∈ Reg Σ, alors L R ∈ Reg Σ.
• L'automate produit permet de paraller les chemins d'un automate A1 et d'un automate A2.
• Si L ∈ Reg Σ, alors L ∈ Reg Σ.
• (Σ⋆, ·) est un monoïde : c’est un groupe non commutatif mais sans la notion d’inverse.