regex - 我想要正则表达式（自动机理论）

Question

考虑字母表 V={0, 1, ..., 9} 和语言 L，它由 V 的所有字符串组成，表示所有大于 798 的整数（例如，字符串 799、890、2345、777777 属于到语言 L，而字符串 1、42、711、798 没有）。提供生成语言 L 的所有字符串的正则表达式

Answer 1

采用完全经典的正则表达式（即析取、连接和 kleene 星号）：

(799|(8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

如果您允许典型的正则表达式速记（但保持在理论限制内，即常规语言），则可以简化为：

799|[89]\d{2,}|[1-9]\d{3,}

您匹配数字 799，一个以 8 或 9 开头的三位数字，或一个以除 0 以外的任何数字开头的四位（或更多）位数字（禁止0023匹配）。