Langage Formel ET Théorie des Automates

Ajit Singh, Zidane Doctio Tsague

• Éditeur: Babelcube Inc.
• Année: 2022
• ISBN de l'eBook: 9781667429786
• Sujet: Informatique
• Sujet: Sciences générales de l'informatique

Le livre contient une couverture approfondie de tous les sujets liés à la théorie du calcul tels que mentionnés dans les programmes de B.E., M.C.A. et M.Sc. (Informatique) de diverses universités. Une quantité suffisante d'apports théoriques soutenus par un certain nombre d'illustrations sont incluses pour ceux qui s'intéressent profondément au sujet. Dans les premiers chapitres, le livre présente le matériel de base nécessaire à l'étude des théories des automates. Exemples de sujets inclus : langages réguliers et théorème de Kleene ; automates minimaux et monoïdes syntaxiques ; la relation entre les langages sans contexte et les automates à pile ; et les machines de Turing et la décidabilité. Ce livre facilite aux étudiants un style d'écriture plus informel tout en offrant la couverture la plus accessible de la théorie des automates, un traitement solide sur la construction de preuves, de nombreuses figures et diagrammes pour aider à transmettre des idées et des encadrés pour mettre en évidence le matériel connexe. Chaque chapitre offre une abondance d'exercices pour un apprentissage pratique.

Chapitre 1

Préliminaires mathématiques : ensemble des fonctions et des relations

––––––––

Ensembles

Un ensemble est une collection d'objets bien définis. Habituellement, l'élément d'un ensemble a des propriétés communes. Par ex. tous les étudiants qui s'inscrivent à un cours « théorie du calcul » constituent un ensemble.

Exemples

L'ensemble des entiers positifs pairs inférieurs à 20 peut être exprimé par

E = {4, 6, 8, 10, 12, 14, 16, 18}

Soit E = {x | x est pair et 4<x<20}

Ensembles finis et infinis

Un ensemble est fini s'il contient un nombre fini d'éléments. Et infini sinon. L'ensemble vide n'a pas d'élément et est noté ɸ.

Cardinalité de l'ensemble

C'est un nombre d’éléments dans un ensemble. Le cardinal de l'ensemble E est | E | = 8.

Sous-ensemble

Un ensemble A est sous-ensemble d'un ensemble B si chaque élément de A est aussi élément de B et est noté A ⊆ B

Tout au long de ce livre, nous supposerons que vous connaissez les mathématiques suivantes concepts mathématiques :

1. Un ensemble est une collection d'objets bien définis. Les exemples sont (i) l'ensemble de tous les médaillés d'or olympiques néerlandais, (ii) l'ensemble de tous les pubs d'Ottawa et (iii) l'ensemble de tous les nombres naturels pairs.

1. L'ensemble des nombres naturels est N = {1, 2, 3, ...}.

1. L'ensemble des entiers est Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}.

4. L'ensemble des nombres rationnels est Q = {m/ n : m ∈ Z, n ∈ Z, n 6 = 0}.

5. L'ensemble des nombres réels est noté R.

6. Si A et B sont des ensembles, alors A est un sous-ensemble de B, écrit A ⊆ B, si tout élément de A est aussi un élément de B. Par exemple, l'ensemble des nombres naturels pairs est un sous-ensemble de l'ensemble de tous les nombres naturels. Tous ensemble A est un sous-ensemble de lui-même, c'est-à-dire A ⊆ A.

L'ensemble vide est un sous-ensemble de chaque ensemble A, c'est-à-dire ∅ ⊆ A.

7. Si B est un ensemble, alors l'ensemble de puissance P (B) de B est défini comme étant l'ensemble de tous les sous-ensembles de B :

P (B) = {UNE : UNE B}.

⊆	P (B) et B ∈ P (B).
Observez que ∅ ∈

Opérations d'ensemble

1. Union

L'union de deux ensembles a des éléments, les éléments de l'un des deux ensembles et éventuellement des deux. L'union est notée AU B.

2. Intersection

L'intersection de deux ensembles est la collection de tous les éléments des deux ensembles qui sont communs et est notée A ⋂ B.

1. Différences

La différence de deux ensembles A et B, notée A - B, est l'ensemble de tous les éléments qui sont dans l'ensemble A mais pas dans l'ensemble B.

1. Le produit cartésien de A et B est défini comme

UNE × B = {(x, y) : x ∈ A et y ∈ B},

1. Le complément de A est défini comme

A' = {X : X 6 ∈ UNE}

Séquences et tuples

Une séquence d'objets est une liste d'objets dans un certain ordre. Par exemple, la séquence 7, 4, 17 serait écrite sous la forme (7, 4, 17). Dans l'ensemble, l'ordre n'a pas d'importance, mais dans la séquence, il l'est. De plus, la répétition n'est pas autorisée dans un ensemble mais est autorisée dans une séquence. Comme set, la séquence peut être finie ou infinie.

Relations et fonctions

Une relation binaire sur deux ensembles A et B est un sous-ensemble de A×B. par exemple, si A = {1, 3, 9}, B = {x, y}, alors {(1, x), (3, y), (9, x)} est une relation binaire sur 2-ensembles. Les relations binaires sur les K-ensembles A1, A2, ........ Ak peuvent être de même défini.

Une fonction est un objet qui configure une relation entrée-sortie, c'est-à-dire qu'une fonction prend une entrée et produit la sortie requise. Pour une fonction f, d'entrée x, la sortie y, on écrit f (x) = y. On dit aussi que f envoie x sur y.

Une relation binaire r est une relation d'équivalence si R satisfait :

R est réflexif. C’est-à-dire pour tout x (x, x) є R.

R est symétrique c'est-à-dire que pour tout x et y, (x, y) є R implique (y, x) є R.

R est transitif i..e. pour chaque x, y et z, (x, y) є R et (y, z) є R implique (x, z) є R.

Fermetures

Les fermet...

Table des matières

• Page de Titre
• Droits d'Auteur
• Droits d'Auteur
• Préface
• Dévouement
• Ceci est pour vous,
• Reconnaissance
• Contenu
• Chapitre 1 | Préliminaires mathématiques : ensemble des fonctions et des relations
• Chapitre 2 | Automates finis (AFD et AFN, Epsilon AFN)
• Chapitre 3 | Expression régulière (RE) et langage)
• Exercer
• C+hapitre 4
• G+rammaires et langages sans contexte
• Chapitre 5 | Automates à pile(PDA)
• Chapitre 6 | Machine de Turing
• Décidabilité de la langue
• Indécidabilité
• Vos critiques et vos recommandations personnelles feront la différence
• Êtes-vous en quête d’autres bonnes lectures ?