Qu'est-ce qu'un exemple simple d'un langage récursivement énumérable qui n'est pas libre de contexte? Mon manuel est horrible en fournissant un tel exemple explicitement.Exemple d'un langage récursivement dénombrable qui n'est pas libre de contexte
Pour être clair, ce n'est pas une question hmk.
La classe de récursivement-énumérable est très large en effet. Il comprend toute langue pour laquelle il existe une machine de Turing qui stoppera et acceptera n'importe quelle chaîne dans la langue (sans que la machine de Turing ne doive s'arrêter si on lui donne une chaîne qui n'est pas dans la langue). Donc un exemple d'un langage récursivement énumérable est l'ensemble H de descriptions (dans un certain formalisme) de machines de Turing qui s'arrêtent sur une entrée donnée. Comme il existe une machine de Turing qui simule n'importe quelle machine de Turing (la machine de Turing Universal), des chaînes valides dans H peuvent certainement être reconnues, mais l'indécidabilité du problème d'arrêt montre que H n'est pas récursif.
Toute machine de Turing peut être représentée comme une grammaire formelle sans restriction (et par conséquent une grammaire formelle est une description d'une machine de Turing). (La construction actuelle est fastidieuse sinon herculéenne et je ne suggère pas de l'essayer.) Ainsi toute machine de Turing pour laquelle le problème d'arrêt est indécidable définit un langage récursivement énumérable qui n'est pas contextuel (ou même contextuel).
Sur un plan plus pédant, des exemples de langages contextuels qui ne sont pas hors-contexte comprennent:
{ ap | p is prime }
{ anbncn | n ≥ 0 }
{ α | α ∈ {a, b, c}* ∩ #a(α) = #b(α) ∩ #b(α) = #c(α) }
(Dans la dernière, #x(α) est le nombre d'occurrences de x dans α Dans d'autres. mots, c'est l'ensemble des chaînes contenant le même nombre de a s, b s et c s.)