Site web du cours : Références wikipedia : Définitions :

Unsa

Description

Site web du cours : Références wikipedia : Définitions :

Sujets

• Arts

Informations

• Publié par: olonilux
• Nombre de lectures: 45
• Langue: Français

Extrait

Mathématiques discrètes

SI3 et MAM3 2008/2009

Résumé de cours

1 : mots et langages

Page 1 sur 2

Site web du cours :

o

http://www.polytech.unice.fr/~claudine/md08

Enoncés et solutions des exercices, des examens

Références wikipedia :

o

http://fr.wikipedia.org/wiki/Langage_formel

o

http://fr.wikipedia.org/wiki/Mathématiques_discrètes

Définitions :

z

A

alphabet

: ensemble dont les éléments sont appelés

lettres

/

symboles

{a, b, .., z}, {0, 1, 2, …, 9},

{0.1}, {class, if, then, while, …}

Notés A ou

∑

ou …

z

Mot

écrit avec les lettres de A ou

Mot

écrit sur l'alphabet A :

suite finie

de lettres de A.

Notés m, u, v, w, …

Dans les langages de programmation, on parle plutôt de

chaîne

(= mot) et de

caractères

(= lettres): par

exemple, classes String et Character en Java, et toutes les fonctions ou opérations qui suivent sont

disponibles en Java.

z

Longueu

r

d'un mot u = nombre de lettres du mot u

Notée |u| : longueur de u

|122333| = 6

Pour tout mot u, on peut parler de la

ième lettre

de u, pour tout entier compris entre 1 et |u|.

Notée u

i

ou u(i) : ième lettre de u

z

Nombre d'occurrences

d'une lettre

a dans

un mot u = nombre de fois où la lettre a est utilisée pour écrire

le mot u

Notée |u|

a

: nombre d'occurrences de la lettre

a

dans le mot u |1221321|

2

= 3

z

A

+

désigne l'ensemble des mots de longueur au moins 1 que l'on peut écrire sur l'alphabet A

z

Tout ensemble de mots est appelé

langage

Le langage des mots de longueur paire.

Le langage des lettres = alphabet.

Notés L, X, Y, Z, …

z

Opération sur les mots :

concaténation

de 2 mots

coller

2 mots

concaténer

2 mots

Notée par un point : u.v ou par simple juxtaposition des 2 mots : uv

si u = ab et si v = ba, uv = abba

Notation : u

n

est la concaténation de n fois le mot u où u est un mot et n un entier non nul.

Opération associative, mais pas commutative.