形式语言与自动机2023春季期末试题回忆版

捏 今天刚考完,趁着记忆清晰,先放上来
题只能说大概一致,仅供参考

  1. Design a DFA on $\Sigma=\{a,b,c\}$, which accepts the string that there is at least one $b$ between any two $a$s
  2. Design an NFA equivalent to $a^*b^*c^+$ with 3 states
  3. Design regular expressions on $\Sigma =\{a,b\}$
    1. strings that substring $aa$ occurs at most two times
    2. strings starts with $bb$ and the length of string is divisible by 4
  4. Prove that $\{w| w\ \mathrm{which}\ 0\ \mathrm{occurs\ more\ than} 1 $}$ is not regular with pumping lemma
  5. Prove $L_1 \cup L_2$ is not regular if $L_1$ is regular $L_2$ is not regular and $L_1 \cap L_2 = \varnothing$
  6. $L=\{a^nb^n | n\geq 0\}$, design a context free grammer for $\overline{L}$, $\overline{L}$ means the complement of $L$ to $\Sigma^*$
  7. Design a DPDA for $\{a^ib^j |i\geq 1,\ j\geq i+3\}$
  8. Give a grammer $G_0$:$$ S \rightarrow aAA|aBB$$ $$A\rightarrow aaA|\epsilon$$$$B\rightarrow bBB|bbC$$$$C\rightarrow B$$
    1. Eliminate ε-productions.
    2. Eliminate any unit productions in resulting grammar.
    3. Put the resulting grammar into Chomsky Normal Form.
  9. G: $$S\rightarrow AB|aaB$$$$A\rightarrow aA|a$$$$B\rightarrow b$$
    1. Show that this grammar is ambiguous
    2. Find a grammar for the same language that is unambiguous
  10. Design a Turing Machine that turn $0^m$ to $0^{m \mod 5}$ such as $f(0^7) = 00$ and $f(0^5) = \epsilon$

如果你在期末考试前读到了这个文章,那祝你考试顺利

形式语言与自动机 部分英文单词对应

Anglais Chinois
string 字符串
alphabet 字母表
substring 子串
determinism 确定性
nondeterminism 非确定性
Deterministic Finite Automata DFA
finite 有穷
infinite 无穷
every run of 0s 0的每一趟~1
prefix 前缀
differ by n 相差n
even 偶数
odd 偶数
appear/occurrence 出现
symbol 符号
induction on 于...的归纳
consecutive 连续的
divisible by 5 可被5整除的
binary 二进制
integer 整数
be interpreted as 被解释为/被当做~2
a multiple of 5 5的倍数
in reverse 反转的
string consisting of 由...组成的字符串
nonempty 非空
transition table 转换表
proof/demonstrate/show/prove 证明/说明
inductive hypothesis 归纳假设
digit 数字
separated by 被...分开
regular 正则
regular expressions 正则表达式
suffix 后缀
contain 包含
except 除了
such that 使
adjacent 相邻的
set 集合
equal 相等的
closure 闭包
simplify 简化
transition diagram 转移图
eliminating 消除
pumping lemma 泵引理
perfect square/cube 完全平方/立方
prime 质数
common divisor 公约数
quotient
proper prefix 真前缀
states 状态
minimize 最小化
homomorphism 同态
context-free laugnage 上下文无关语言
grammar 语法
variables 变元
terminals 终结符
productions 产生式/产物
repeated 重复的
twice as many 0’s as 1’s 0是1的二倍
rightmost derivations 最右派生
derivation 派生
right-linear 右线性
a sequence of 一连串
ambiguous 歧义的
unambiguous 非歧义的
parse tree 语法分析树
operands 操作数
unit productions 单元产生式
Chomsky Normal Form 乔姆斯基范式
recursively 递归的
blocks 块,理解同runs
pushdown automata PDA,下推自动机
empty stack 空栈
final state 接受状态
Turing machines TM,图灵机
  1. eg. every run of 0s has length at least 3有0时只能是000或更多连续0
  2. eg. be interpreted as binary integer

感谢Doctor Z.制作的形式语言与自动机的英文单词对照,如果能帮到大家的话十分荣幸

六级出分了

过了,454。
不过比较悲剧的是,研究生免读分数线是460。

Practice

Calligraphy 的重拾与杂谈

令人伤心的是 这次是我的第二次动笔,第一次已经写了大半的文字已经遗失,第二次写作可能也没有第一的那种欢愉与快乐了

很难想象的,我已经接触英文书法接近十年了。在这近十年的碌碌无为的时光匆匆过去之后,我的水平近乎于初学者,就连最基本的东西也会觉得无从下手。

我不敢惶恐的把这件事情归咎于学业之类的压力之上,或许我可以迁就自己而为自己开脱,而言说自己近十年只有几个能量高峰期,而其他时刻对于calligraphy 的热情总是烟消云散而常常被遗忘。

可能近段时间我又迎来人生中对于calligraphy 少有的几个能量高峰期吧。虽然在撰写这篇文章的时候已然停笔而咕咕了有近一个月时间了。 我又一次重新拾起近十年前的笔尖而书于纸上。

终究觉得lessons in roundhand 是为ER流派所撰写的一本教材,我又回想起早些年,或者说儿时,也就是接近十年前用着老旧的ThinkPad 上阅读的那本教材,但我也早已忘记了那本书的名字,唯一有所印象的是那本书是一个叫做什么D博士又亦或是XYZ博士所写的教材。翻遍了Onedrive、度娘网盘亦或是本地上的磁盘,我却很难在其中找到些许痕迹。不过凭借依稀对于一位英文书法类贴吧的吧主的昵称有所印象,我还是翻到了那一本书的帖子。比较幸运的是,这些珍贵的帖子并没有在多年前百度贴吧经历的那场大浩劫中所遗忘,甚至这个接近十年的百度云链接也没有被度娘吞噬掉。

今日能够重读Script in the Copperplate Style: Engrosser’s Script,诚然是一种荣幸。(教材在文末有分享)私以为这本作为ES流派的入门参考教材是较为友好的。没有什么长篇大论而是简洁的给出来基本笔画的书写方式,以及基本笔画如何组合出来小写与大写字母。我所练习的ES大多数时期都是基于这本教材的。唯一的问题同样也在于文字说明较为单薄,有一些字母,尤其是大写字母,需要亲自去书写,亲自去思考才能体会。

今日份练习的丑照

今日份练习的丑照 勿喷

今日所练习的是大写字母的基本笔画部分,在我见得,对于ES而言,核心问题是如何把直线写的更直而没有抖动亦有对于粗细把握的稳定性、对于各类圆大小的掌握以及圆润度的掌握以及把各种圆以合适的角度合适的位置以连续稳定的回环拼起来的技术。优秀的calligraphier(?不知道可不可以这么说)对笔的稳定性把握是极强的,对于初学者来说可能感受到的是大笔画粗细的把握,而今日我突然发现其实最为难以掌握的实际上是各类的游丝,往往令人懊恼。过细的笔画在手不稳时候会出现及其明显的抖动,并且游丝对于手法的要求极高,不小心导致笔尖弹开是非常常见的事情。

不得不说,本人的基本功水平仍然处于谷底,十分欠缺。我还是没能够做好基本的稳定性。唯有希望我能够多坚持一下这个短暂的能量波峰,勤加练习,才能有所长远的进步。
Script in the Copperplate Style: Engrosser’s Script

Practice

我回来了

是的,咱的blog在高中时期断断续续维持了一段时间,咱也没更新几篇文章。现在,是时候回来了。XD

这个blog估计不全是技术向的内容,可能会包含其他杂七杂八的东西比如Copperplate练习、随想云云。

一切看心情啦。

喵呜