Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Prepa (autre)
Partager :

Grammaire

Posté par
elgrando2001 10-01-23 à 23:46

* Modération >   *** Bonjour *** *

Je trouve de difficulte pour resoudre ça : en utilisant des proprieté mathematique pertinente (ensemble... ) trouvez une langage engendré par cet grammaire :

S->0A|0|1B, A->1A | 1, B->0B | 1S

Posté par
Ulmierere : Grammaire 11-01-23 à 11:04

Il est clair que A = 1^\ast
Applique une variante du théorème d'Arden à B (ou fais comme A, et dit que ça se voit) pour trouver B = 0^\ast 1S

Ensuite, S = (01^\ast + 0) + 1(0^\ast 1S) = (01^\ast) + (10^\ast 1)S

Donc tu réappliques le théorème d'Arden, cette fois à S pour trouver

S = (10^\ast 1)^\ast 01^\ast


Maintenant, ou bien tu vois direct la simplification de cette expression régulière, ou bien tu dessines le graphe de l'automate (fini non déterministe) qui correspond à cette expression régulière.
Ensuite, tu le transformes en automate fini déterministe (avec surement plus d'états) sur lequel tu appliques l'algorithme de minimisation de ton choix.
Tu en déduis un système d'équations à résoudre en utilisant l'associativité de la concaténation et le lemme d'Arden, un peu comme on a fait là.
Et tu auras peut-être une expression régulière un peu plus claire.

Posté par
Ulmierere : Grammaire 11-01-23 à 11:06

Y'a des erreurs dans mes petits calculs, j'ai lu trop vite.
A = 1^+, et non A = 1^\ast.

Tu peux l'écrire A = 11^\ast si tu veux, et faire le reste du calcul pareil

Posté par
elgrando2001re : Grammaire 11-01-23 à 14:25

Apres une rectification des calcule on aura :
S=(011*+0)+(10*1)S
Comment peut on appliquer le lemme d'arden ppur eliminer la deuxieme S et trouvez l'expression reguliere qui le correspond

Posté par
Ulmierere : Grammaire 11-01-23 à 16:29

Ca se simplifie encore

(01^+ + 0) = 0(1^+ + \varepsilon) = 01^\ast


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !