计算的基本理论复习-华中科技大学

系统管理员 2023-01-01 08:54 103阅读 0赞

> 昨天刚考完计算的基本理论  
> 这门课主要讲了离散数学里面的集合，形式语言与自动机  
> 听起来很编译原理  
> 非常喜欢FC老师讲课的风格  
> 看我们考试做题很艰难，他说早知道出简单一点了 这会儿出去跨年 光谷步行街都关门了  
> 哈哈

**复习资料：**

--------------------

1.设R是基数为n的集合A上的关系，试证明R的传递闭包 R + = ⋃ i = 1 n R i R^\{+\}=\\bigcup\_\{i=1\}^\{n\}R^\{i\} R\+=⋃i=1nRi

--------------------

2.设连通图G=(V,E)是(n,m)图，且无环时，证明：m = n-1

--------------------

3.设 L 1 , L 2 L\_\{1\},L\_\{2\} L1,L2是 ∑ \\sum ∑上的语言，求证： ( L 1 ⋃ L 2 ) ∗ = ( L 2 ∗ L 1 ∗ ) ∗ (L\_\{1\} \\bigcup L\_\{2\})^\{\*\}=(L\_\{2\}^\{\*\} L\_\{1\}^\{\*\})^\{\*\} (L1⋃L2)∗=(L2∗L1∗)∗

--------------------

4.构造文法产生语言 L 1 = \{ w ∣ w = w T , w ϵ ∑ + \} , ∑ = \{ a , b , c \} L\_\{1\} = \\\{ w | w = w^\{T\} ,w \\epsilon \\sum^\{+\} \\\},\\sum=\\\{a,b,c\\\} L1=\{ w∣w=wT,wϵ∑\+\},∑=\{ a,b,c\}

--------------------

5.构造DFA识别语言 L 1 = \{ x ∣ x ϵ \{ 0 , 1 \} \} L\_\{1\}=\\\{ x| x\\epsilon \\\{0,1\\\}\\\} L1=\{ x∣xϵ\{ 0,1\}\}且当把x看成二进制时x模5与3同余，要求当x=0时，|x|=1且x ≠ 0 \\neq 0 =0时，x的首字符为1

--------------------

6.证明 \{ 0 n ∣ n 为 素 数 \} 不 是 R L \\\{0^\{n\} | n为素数\\\} 不是RL \{ 0n∣n为素数\}不是RL

--------------------

7.求证 \{ x ∣ x ϵ ∑ + , x 倒 数 第 三 个 字 符 为 1 ， ∑ = \{ 0 , 1 , 2 \} \} 是 R L \\\{x | x \\epsilon \\sum^\{+\},x倒数第三个字符为1，\\sum=\\\{0,1,2\\\} \\\}是RL \{ x∣xϵ∑\+,x倒数第三个字符为1，∑=\{ 0,1,2\}\}是RL