Construct DFA pour L = {(na (w) -NB (w)) mod 3> 0}

Question

Selon le titre:

L = {(n _un (w) -n _b (w)) mod 3> 0}

Alphabet = {a, b}

J'ai trouvé deux réponses à ce problème:

Dans cette sorte lution, notre langue est acceptée.

Cependant,

w = b 

est acceptée aussi bien.

Dans la solution suivante:

Notre problème de

w = b 

est résolu ici, mais

w = aaab 

ne sont pas acceptées.

Comment aborder ce problème? Je n'ai pas trouvé de réponse appropriée pour cela sur internet.

Answer 1

Supposons que nous ayons la définition suivante de mod:

x mod y = {  x,  if 0 <= x < y 
      (x - y) mod y, if 0 < y <= x 
        x,  if -y < x < 0 
      (x + y) mod y, if x <= -y < 0 
      -(-x mod -y) if y < 0 
      } 

Donc, notre module fonctionne comme ceci:

3 mod 5 = 3 
6 mod 5 = 6-5 mod 5 = 1 mod 5 = 1 
-3 mod 5 = -3 
-6 mod 5 = -6+5 mod 5 = -1 mod 5 = -1 
-6 mod -5 = -(6 mod 5) = -1 
6 mod -5 = -(-6 mod 5) = -(-1) = 1 

Notre langue est L = {(N_A (w) - n_b (w)) mod 3> 0}

Définissons A := n_a(w) et B := n_b(w). Nous devons donc résoudre (A - B) mod 3 > 0 en utilisant notre définition de mod. Nous avons cinq cas:

1. si 0 < = A - B < 3, ce qui signifie B < = A < B + 3, puis (A - B) mod 3 = A - B. Par hypothèse, il est à moins zéro, et ne peut être nul que si A = B. Nous pouvons confirmer que lorsque A = B nous sommes toujours dans le cas n ° 1 et nous avons toujours (A - B) mod 3> 0 faux, donc nous pouvons lancer cette possibilité en dehors.

2. si 0 = A - B, ce qui signifie B < 3 + B < = A ou simplement A> = 3 + B, puis (A - B) mod 3 = (A - B - 3) mod 3. Par l'hypothèse A - B - 3> = 3 + B - B - 3> = 0, nous sommes toujours dans les deux cas 1 ou 2. Si nous restons dans le cas 2, nous pouvons répéter ceci jusqu'à ce que nous atteignions finalement cas 1, et nous verrons que nous ne pouvons pas avoir A - B - 3k = 0; c'est-à-dire que ça ne peut pas être A = B + 3k pour tout k positif.

3. si -3 < A - B < 0, ou B - 3 < A < B, puis (A - B) mod 3 = A - B. Par hypothèse, il est inférieur à zéro, et donc nous devons jeter toutes ces possibilités.

4. si A - B = -3 < < 0, ce qui signifie A < = B - 3 < B ou simplement un < = B - 3 puis (A - B) mod 3 = (A - B + 3) mod 3. Par l'hypothèse, A - B + 3 < = B - 3 - B + 3 = 0, donc nous sommes toujours dans les deux cas 3 ou 4. Si nous restons dans le cas 4, nous pouvons répéter ceci jusqu'à ce que nous atteignions finalement le cas 3, et nous verrons qu'il ne reste rien.

5. Nous ne pouvons pas être dans ce cas depuis le 3> 0.

Nous avons dû jeter les cordes de notre langue suivantes:

• A = B
• A = B + 3k
• A < B.

Donc nous ne conservons que les chaînes avec plus de a que de b où A - B n'est pas divisible par 3. Supposons que cette langue soit régulière. Considérons la chaîne (b^p) (a^(p + 1)) dans la langue. Par le lemme de pompage, nous devrions être en mesure de pomper le nombre de b s; mais alors nous pourrions obtenir plus de b s que a s. Donc, la langue ne peut pas être régulière.

Si nous prenons ce qui est peut-être une définition plus habituelle pour x mod y (pas plus correct, nécessairement):

x mod y = {  x  , if 0 <= x < y 
       (x - y) , if 0 < y <= x 
      (x + y) mod y , if -y < x < 0 
      -(-x mod -y) , if y < 0 
      } 

Par cette définition:

1. dans le cas 1, nous jetons A = B
2. dans le cas 2, on jette A = B + 3k
3. dans le cas 3, on jette A = B - 3k
4. puisque 3> 0, le cas 4 ne s'applique pas

Maintenant, nous avons seulement rejeté les cas où A mod B = 0 (mod 3). Ce langage est régulier et possède DFA:

+------------a-------------+ 
    |       | 
    | +---b----+ +---b----+ | 
    | |  | |  | | 
    V V  | V  | | 
    (q0)---a--->(q1)---a--->(q2) 
--->(q0) 
    (q0)---b--->(q3)---b--->(q4) 
    ^^  |^  | | 
    | |  | |  | | 
    | +---a----+ +---a----+ | 
    |       | 
    +------------b-------------+