自然语言处理——3.5 形式语言与自动机 习题

3-1. 构造上下文无关文法用以产生：
(a) 有相同数目的和的所有 符号串。
(b) 。

3-2. 有以下文法： 其中：





求

3-3. 写一个程序模拟一个确定性的PDA。

3-4. 设文法由如下规则定义：



给出下列句子形式的派生树:
(1) (2)

3-5. 写一个程序以正则文法 作为输入，构造 相应的有限自动机。

3-6. 实现编辑距离计算方法：对于任意给定的两个相似的英语单词计算出其编辑距离。