小于和大于的正则表达式（不是符号！）

Question

我有一个等于 {0,1} 的集合我想找到所有长度为 3 或更短且 0 多于 1 的字符串。

我只能找到与符号相关的线程。

Answer 1

字符串如下：

可以使用 Myhill-Nerode 找到该语言的最小 DFA。我们开始考虑字符串并判断每个字符串是否与之前的字符串有区别。

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

这为我们提供了以下最小 DFA：

 .
 |
 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-/

小于和大于的正则表达式（不是符号！）

Regular expression for less than and more than (not the symbols!)

expression

regular-language