有限自动机接受的语言可以简单地由称为正则表达式的简单表达式定义。它是描述任何语言的有效方法。正则表达式也可以表示为表示字符串的模式序列。正则表达式用于连接字符串中的字符序列。字符串搜索算法使用此模式来发现对字符串的操作。
正则表达式有多种规则，如下所示 -
ε 是正则表达式。
两个正则表达式R 1和R 2 的并集。
即，R 1 + R 2或R 1 | R 2也是一个正则表达式。
两个正则表达式R 1和R 2 的串联。
即，R 1 R 2也是一个正则表达式。
正则表达式R的闭包，即R*也是一个正则表达式。
如果 R 是正则表达式，则 (R) 也是正则表达式。
R1|R2=R2|R1 or R1+ R2=R2+ R1 (Commutative) R1| (R2|R3)=(R1| R2)|R3 (Associative) Or R1+ (R2+ R3)=(R1+ R2)+R3R1 (R2|R3)=(R1R2)R3 (Associative) R1| (R2|R3)=R1R2| R1R3 (Distributive) Or R1 (R2+ R3)=R1R2+R1R3ε R=R ε=R (Concatenation)
Example1 - 在 $\sum$={a,b} 上为以下语言编写正则表达式
长度为零或一的字符串。
答案：ε | | b 或 (ε+a+b)
长度为 2 的字符串。
答案：aa | AB | bb 或 (aa+ab+ba +bb)
等长字符串
答案：(aa| ab| ba | bb)* 或 (aa+ab+ba +bb)*
至少出现两次 aa 的 a 和 b 的所有字符串的集合。
答案 - (a+b)*aa(a+b)aa(a+b)*
Example2 - 查找以下语言的正则表达式。
L={ε,1,11,111,....}
{∴ 10=ε,11=1,12=11,13=111…..}答案：1*
L={ε,11,1111,111111,.....}
答案：(11) $\ast$
L = 0 和 1 的所有字符串的集合 = {ε,0,1,01,11,00,000,101,……}
答案：(0+1) $\ast$或 (0|1) $\ast$
L = 以 11 结尾的所有 0 和 1 字符串的集合。
答案：(0+1) $\ast$11
L = 以 0 开头并以 1 结尾的所有 0 和 1 字符串的集合。
答案：0(0+1) $\ast$1
Example3 - 编写正则表达式，其中从字符串右端的第二个字母是 1，其中 $\sum$={0,1}。
答案：(0+1) $\ast$1(0+1)
Example4 - 在 $\sum$={a,b} 上为以下语言编写正则表达式
L=至少出现一个双字母的字符串集
答案：(a+b)*(aa+bb)(a+b)*
L = 在字符串的开头和结尾具有双字母的字符串集。
答案：(aa+bb)(a+b)*(aa+bb)
L = 在字符串的开头或结尾具有双字母的字符串集。
答案：(aa+bb)(a+b)*+(a+b)*(aa+bb)+(aa+bb)(a+b)*(aa+bb)