1. Accueil
  2. Question et réponse
  3. Construire un DFA pour la langue suivante: L = {a^n b^n | n> = 1}

Construire un DFA pour la langue suivante: L = {a^n b^n | n> = 1}

2011-02-04 2 views

Répondre

9

Je pense que vous avez mal compris vos devoirs (sans parler des cours eux-mêmes). Cette langue n'est pas régulière. Qu'est-ce que cela signifie, vous ne pouvez pas construire un DFA pour cela. Pensez-y: lorsque vous parcourez la boucle sur a, vous ne détenez nulle part le nombre de fois que vous avez exécuté l'état. Vous n'avez aucun moyen de savoir combien de fois lire b.

Cela peut se faire dans un contexte de grammaire libre comme ceci cependant:

S->aSb|ab

Source

2011-02-04 17:42:46 Blindy

+1

Parfois, je me demande si les fans de downvoters ont même lu le post .. – Blindy

0

Est-ce que vous allez sur le lemme de Pompage régulier dans votre classe?

Il y a un lemme de pompage similaire pour langage algébrique et

Source

2011-02-04 19:33:12

+0

Exemple pour cette langue spécifique: http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma – Flo

+0

ahh cela me ramène :) –

Questions connexes

 Questions connexes