CH.8 Décidabilité
Propriétés des langages récursivement énumérables : Fermés par union mais pas par intersection. Page 2. Automates ch8 3. Théorème : Le langage L est récursif si
05/06 - 2.2.3 Récursivité gauche
Un symbole non terminal A d'une grammaire est dit récursif si A algébrique non récursive gauche qui reconna?t le même langage.
Introduction `a la Programmation des Algorithmes 3.2. Langage C
Langage C – Fonctions récursives. François Fleuret https://fleuret.org/11x001/. On peut définir des fonctions mathématiques de mani`ere récursive.
Calculabilité
décidé par une certaine machine de Turing. Un langage ou un problème décidable est aussi dit récursif. Un langage qui n'est.
INDÉCIDABILITÉ MT ET GRAMMAIRES
Un langage L est récursif ssi L et ¬L sont récursivement énumérables. 10. Preuve. Page 11. Propriétés des langages récursifs.
Thème 1 : la récursivité 1 Rappels sur les fonctions
Pour définir nos fonctions nous utiliserons du pseudo-code ou la syntaxe du langage Python rappelée ci-dessous. Définition de la fonction : def maFonction(x1..
Programmation récursive 1. Quest-ce que la programmation récursive
Définition : la programmation récursive est une technique de programmation qui remplace les question de goût de style et de langage de programmation.
Calculabilité Cours 3 : réductions
L'ensemble des langages décidables avec oracle B est {A
Introduction `a la calculabilit´e
Langages récursifs et récursivement énumérables. Un langage est récursif s'il est décidé par une machine de Turing. Un langage est récursivement énumérable
L3 Informatique Calculabilité 18 septembre 2014 Exercice 1
18 sept. 2014 Exercice 1 (Clôture des langages récursifs) ... Montrer que L est un langage récursivement énumérable si et seulement s'il.
[PDF] Algorithmique Récursivité
Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact
[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif Programmation impérative / fonctionnelle Langage commun entre la machine et nous : Scheme N Guin – M Lefevre
[PDF] Séance 5 : Fonctions récursives et machine de Turing
Or le langage RP est équivalent à une partie du langage Pascal seulement avec la boucle for et sans appels récursifs V 1 2 3- Quelques exemples de fermeture
[PDF] Programmation récursive 1 Quest-ce que la programmation - LIPN
Définition : la programmation récursive est une technique de programmation qui remplace les instructions de boucle (while for etc ) par des appels de fonction
[PDF] La récursivité - Zeste de Savoir
12 août 2019 · La récursivité est un concept général qui peut être illustré dans (quasiment) tous les langages de programmation et qui peut être utile
[PDF] Récursivité
C'est ce qui garantit que le programme s'achèvera Exercice 5 Un programme en langage python : Jean-Manuel Mény – Ludovic Fasquelle – Irem de Lyon
[PDF] Récursivité - LACL
langages de programmation tel que le langage C Bien entendu cela complique l'implémentation d'un tel langage mais facilite la tâche du programmeur
[PDF] Récursivité
On peut citer à ce sujet Guido van Rossum le créateur du langage Python : I don't believe in recursion as the basis of all programming This is a fundamental
[PDF] Thème 1 : la récursivité 1 Rappels sur les fonctions
Pour définir nos fonctions nous utiliserons du pseudo-code ou la syntaxe du langage Python rappelée ci-dessous Définition de la fonction : def maFonction(x1
2.2.3 R´ecursivit´e gauche
Un symbole non terminalAd"une grammaire est ditr´ecursifsiA?-→αAβavecα,β? (X?V)?. Siα=ε,Aest ditr´ecursif (`a) gauche. Une grammaire comportant au moins un symbole non terminal r´ecursif gauche est dite r´ecursive gauche. (Idem droite). La r´ecursivit´e gauche pose divers probl`emes en analyse,et dans l"application de certains algorithmes de transformation de grammaire. C"est la raison pour laquelle on cherche `a´eliminer cette r´ecursivit´e, ce qui est toujours possible, car on dispose d"un th´eor`eme :
Tout langage alg´ebrique peut ˆetre g´en´er´e par une grammaire alg´ebrique non r´ecursive gauche La d´emonstration de ce th´eor`eme, comme souvent en pareilcas, repose sur un algorithme qui, ´etant donn´ee une grammaire alg´ebrique r´ecursive gauche, produit une grammaire alg´ebrique non r´ecursive gauche qui reconnaˆıt le mˆeme langage. Il faut proc´eder en deux temps : d"une part, on va ´eliminer lar´ecursivit´e directe(ou imm´ediate), puis ´eliminer lar´ecursivit´e indirecte. On pr´esente ici l"algorithme en
commen¸cant par un cas simple, qu"on g´en´eralise avant d"´eliminer finalement toutes les
r´ecursivit´es. R`egle simpleAu niveau d"une r`egle, cela peut se faire simplement : A→Aα|β, (avecβ?=Au), devient :A→βA? A ?→αA?|ε La r`egleA→Aαpermet de g´en´erer un nombre quel- conque de chaˆıne(s)α, mais pour que la d´erivation soit effectivement productive, il est n´ecessaire que la r´ecursion s"arrˆete, c"est-`a-dire queAdonneβ. On charge alors une r`egle de commencer par ceβ, et ensuite on a une r`egle r´ecursive (mais pas gauche), pour engendrer autant de fois que n´ecessaire lesα.A A A Aβ A
α A?
???αA? Bien entendu, on produit un arbre syntaxique diff´erent dansles deux cas. G´en´eralisationPour chaque non terminal r´ecursif, on propose : A ?-→α1A?|α2A?|...|αmA?|εExempleE-→E+T|T
T-→T?F|F
F-→(E)|ase trouve transform´e enE-→TE? E ?-→+TE?|εT-→FT?
T ?-→ ?FT?|εF-→(E)|a
Appliqu´e `a chaque non terminal r´ecursif, cet algorithmesupprime les sources de r´ecursivit´e
8 Universit´e Paris 7 - LI324 - 05/06Ch2. Langages alg´ebriques gauchedirectes. Mais, comme on peut le voir avec l"exemple suivant, il y a potentiellement dans les grammaires des sources de r´ecursivit´e indirectes, qu"il faudra ´eliminer aussi.S-→Aa|b
A-→Ac|Sd|cqui devientS-→Aa|bR`egle conserv´eeA-→SdA?|cA?R`egle transform´ee
A ?-→cA?|εLa r´ecursivit´e directe de la r`egleA-→Aαest supprim´ee, mais on n"a pas ´elimin´e la
r´ecursivit´e indirecteA-→Sγ-→Aα?γ.Elimination de la r´ecursivit´e indirecte
Id´ee de l"algorithme : pour les paires de r`egles du typeA→A?δetA?→Aη, on"anticipe»
les d´erivations probl´ematiques :A→Aηδ, et on applique l"algorithme pr´ec´edent.
Suppression de toutes les r´ecursivit´es
Donn´eesGgrammaire alg´ebrique propre
R´esultatG?grammaire sans r´ecursivit´e `a gauche, t.q.LG=LG?. M´ethodeSoit (A1,A2,...An) la liste ordonn´ee desAi?V.Pour toutide 1 `anfaire{
Pour toutjde 1 `ai-1 faire{
SiAi-→Ajαexiste, la remplacer par :Ai-→δ1α|δ2α|...|δhα o`uAj-→δ1|δ2|...|δh ´Eliminer la r´ecursivit´e imm´ediate desAi-productions Exemple : grammaire pr´ec´edenteS-→Aa|bA-→Ac|Sd|c
Ordre des non-terminaux (arbitraire) :{A1=S,A2=A}
-i= 1 :∅ -i= 2;j= 1 : - La r`egleA-→Sdest concern´ee (Ai(=2)→Aj(=1)α) - On la remplace parA-→Aad|bd - On"d´er´ecursive»toutes lesA(i)-productions : Les r`eglesA→Aad|Ac|c|bddeviennent?A-→cA?|bdA? A ?-→adA?|cA?|ε - FinLa grammaire r´esultante est?????S-→Aa|b
A-→cA?|bdA?
A ?-→adA?|cA?|εou?????S-→Aa|bA-→cA?|bdA?|c|bd
A ?-→adA?|cA?|ad|c ExerciceAppliquer le mˆeme algorithme `a la grammaire suivante, grammaire de la liste.S→(L)|a
L→L,S|S
9quotesdbs_dbs45.pdfusesText_45[PDF] fonction primitive récursive exercice corrigé
[PDF] théorème de godel démonstration
[PDF] codage de godel
[PDF] théorème de gödel pdf
[PDF] arithmétique de robinson
[PDF] nombre de godel
[PDF] godel dieu
[PDF] théorème d'incomplétude pour les nuls
[PDF] incomplétude définition
[PDF] introduction ? la calculabilité pdf
[PDF] indemnité prof principal 2017
[PDF] isoe prof principal
[PDF] hsa prof
[PDF] indemnite tuteur stagiaire education nationale
