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

Question

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

的所有字符串的正则表达式

Answer 1

使用完全经典的正则表达式（即析取、串联和 kleene star）：

(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 匹配） .

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

I want regular expression (theory of automata)

regex

automata-theory