Licence Creative Commons Preuve par consistance (L(G) dans L)

13 novembre 2020
00:07:15
Nombre de vues 77
Nombre d’ajouts dans une liste de lecture 0
Nombre de favoris 0
Démonstration de la consistance entre L = { w ∈ (A+B)* tq #(w,a) = #(w,b) } et  L(G)   où  G est la grammaire définie par les règles  :  R1) S → aSbS ;   (R2) S → bSaS ;   (R3) S → ε
C'est une preuve par induction structurelle d'une propriété. La propriété P choisie est  P(σ) = [ f(σ)=0 ] où f(σ) = #(σ,a) - #(σ,b), et est montrée comme vrai sur Sent(G), l'ensemble des formes sententielles. La preuve sur L(G) se termine en coupant Sent(G) sur le vocabulaire terminal : L(G) = Sent(G) ∩ T*

Mots clés : analyse syntaxique

Commentaire(s)