Skip to content

Languages

:material-circle-edit-outline: 约 200 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

S 的力集表示为 \(P(S)\) 或 \(2^S\)，包含所有 \(S\) 的子集，类似函数依赖的闭包概念

集合的逆 inverse

字母表与语言

语言的逆表示为 \(w^R\)

有限字母表产生可数有限语言

image-20240927183234578

Kleene 星号 \(L^*=L^0\cup L^1\cup...\)

\(L^+=L^1\cup...=L\cup L^*\)

\(\empty ^*={e}\)

\((L ^*)^*=L ^*\)

\(L\empty = \empty L=\empty\)，因为空语言中没有串

？？？？

正则表达式

  • 有限语言等价于正则语言
  • $\Sigma^\star $ 是正则语言
  • 正则语言的子语言未必正则

一般用 R 表示正则表达式，用 L(R) 表示正则表达式对应的语言（匹配的字符串集合）。

image-20240929153842122

大括号表示一个字母表

下面这个函数构建了正则表达式与语言集合之间的映射：

image-20240929155048160

\(\{a\cup b\}^*=\{a,b\}^*\)

image-20240929155223588