Home 形式语言与自动机 - 基本概念
Post
Cancel

形式语言与自动机 - 基本概念

引言

Sometimes it’s the people who no one imagines anything of who do the things that no one can imagine

最近从毕导视频弹幕中得知关于图灵的记录片 The Imitation Game(模拟游戏),顺便看了一下,对于片中出现的该句话感触颇深,以此当作形式语言与自动机文章的开篇题引

当您开始有点抑郁的时候,也请看看 Amy 关于此句的感悟

基本概念

字母表:符号 (字符) 的非空又穷集

\[{\textstyle \sum_1} = \{0, 1\}\]

字符串:由某字母表中符号组成的有穷序列

\[若 \space {\textstyle \sum_1} = \{0, 1\},那么 \space 0,1,00,101011 \space 为 \space {\textstyle \sum_1} \space 上的字符串\]

空串:记为 $\varepsilon$ ,有 0 个字符的串。对任意字母表 $\sum$ 都有 $\varepsilon \notin \sum$

符号的使用约定

字母表:$\sum, \Gamma, \cdots$

字符:$a, b, c, \cdots$

字符串:$\cdots,w,x,y,z$

集合:$A,B,C,\cdots$

字符串的长度:字符串中符号所占位置的个数

\[对于 \space {\textstyle \sum_1} = \{0, 1\},|0010|=4\]

字符串 $x$ 和 $y$ 的连接:将首尾相接得到新字符串的运算,记为 $x \cdot y$ 或 $xy$

\[x=01, y=ab, 则 \space xy=01ab\]

字符串 $x$ 的 $n$ 次幂 ($n \ge 0$) ,递归定义为

\[x^n= \left \{ \begin{matrix} \varepsilon & n=0 \\ x^{n-1}x & n \gt 0 \end{matrix} \right .\]

$对于 \space {\textstyle \sum_1} = {a, b} (ba)^2=baba, ba^2=baa$

集合 $A$ 和 $B$ 的连接,记为 $A\cdot B$ 或 $AB$ ,定义为

\[A \cdot B = \{ w |w=x \cdot y, x \in A \space and \space y \in B \}\]

若 $\space A = {0, 11} \space B = {ab, ba} $
$AB = { 0ab, 0ba, 11ab, 11ba }, BA= { ab0, ab11, ba0, ba11 }$

集合 $A$ 的 $n$ 次幂 ($n \ge 0$) ,递归定义为

\[A^n= \left \{ \begin{matrix} \{ \varepsilon \} & n=0\\ A^{n-1}A & n \ge 1 \end{matrix} \right .\]

$对于 \space {\textstyle \sum_1} = {0, 1} $,有 ${\textstyle \sum^0}={\varepsilon}, {\textstyle \sum^1}={0,1}, {\textstyle \sum^2}={00,01,10,11}, \cdots$

克林闭包 (Kleene Closure) : 将某字母表的所有幂 (包含零次) 去并集得到

\[{\textstyle \sum^*} = \bigcup_{i=0}^{\infty}{\textstyle \sum^i}\]

正闭包 (Positive Closure) : 将某字母表的所有幂 (不包含零次) 去并集得到

\[{\textstyle \sum^+} = \bigcup_{i=1}^{\infty}{\textstyle \sum^i}\]

显然

\[{\textstyle \sum^*} = {\textstyle \sum^+} \cup \{ \varepsilon \}\]

语言

定义:若 $\sum$ 为字母表且 $\forall L \subseteq \sum^*$ ,则 $L$ 称为字母表 $\sum$ 上的语言

  • 自然语言、程序设计语言等
  • $ \{ 0^n 1^n \mid n \ge 0 \} $
  • The set of strings of 0’s and 1’s with an equal number of each
  • $\emptyset$ ,${ \varepsilon }$ 和 $\sum^*$ 分别都是任意字母表 $\sum$ 上的语言,但 $\emptyset \ne { \varepsilon }$

语言唯一的约束就是所有字母表都是有穷的

This post is licensed under CC BY 4.0 by the author.

Vue 学习

东京科学大学大学院情报理工学院 2020 问题一 / 科学大院理工学 2020 問題一