Expression régulière pour moins de et plus de (pas les symboles!)

Question

J'ai un ensemble qui vaut {0,1} Je veux trouver toutes les chaînes de longueur 3 ou moins qui ont plus de 0 que de 1.

Je ne peux trouver que les threads relatifs aux symboles.

Answer 1

Les chaînes sont les suivantes:

0 
00 
001 
010 
100 
000 

Un DFA minimal pour la langue peut être trouvée en utilisant Myhill-Nerode. Nous commençons à considérer les chaînes et à dire si chacune se distingue des précédentes.

e: can be followed by L, distinguishable 
0: can be followed by e,0,01,10,00,00; distinguishable 
1: can only be followed by 00; distinguishable 
00: can be followed by e, 0 or 1; distinguishable 
01: can be followed by 0 only; distinguishable 
10: can be followed by 0 only; indistinguishable from 01 
11: can never lead to a string in the language; distinguishable 
000: can be followed by e only; distinguishable 
001: can be followed by e only; same as 000 
010: can be followed by e only; same as 000, 001 
100: can be followed by e only; same as 000, 001, 010 
???: all other strings of length 3 never lead to a string in L, like 11 
????: strings of length over 3 never lead to a string in L, like 11 

Cela nous donne la DFA minimale suivante:

. 
| 
v 
(e)--0-->(0)---0-->(00) 
|  |   | 
1  1   0,1 
|  |   | 
v  v   V 
(1)--0-->(01)--0-->(000) 
|  |   | 
1  1   0,1 
|  |   | 
v  v   v 
(11)<--\--/----------/ 
| ^
|  | 
\-0,1-/