形式语言与自动机_课件_陈有祺第04章 正则表达式.ppt

第四章 正则表达式 正则表达式的定义 正则表达式和有穷自动机的关系 正则表达式的等价变换 正则表达式的应用 正则表达式的定义 定义 4.1 设是一个字母表上的正则表达式以及由它们代表的集合递归地定义如下 (1) 是一个正则表达式它代表空集 (2) 是一个正则表达式它代表集合{} (3) 对于中每个符号a , a是正则表达式它代表集合{a} (4) 如果r和s是正则表达式它们分别代表集合R和S则(r