1、无产生式的上下文无关文法要满足条件 若P中含S   ，则S不出现在任何产生式右部，其中S为文法的开始符号； P中不再含有其它任何产生式。 2、构造无产生式的上下文无关文法变换算法： G=(VN,VT,P,S) G’=(V’N,V’T,P’,S’) （1）由文法G找出所有经过若干步推导能推出的非终结符，放在V0集合中。

形式语言与自动机：第八讲 上下文无关文法-下推自动机

形式语言与自动机：第二讲 上下文无关文法与上下文无关语言

PDA计算过程 一台下推自动机M= (Q,,,,q0,F)的计算过程如下： 它接受输入ω，如果能够把ω写成ω=ω1ω2ωm，这里ωi∈，并且存在序列r0,r1,,rm∈Q和字符串序列s0，s1,,sm∈*，满足下面三个条件，字符串si是M在计算的接受分支中的栈内容序列 r0=q0，且s0=ε，表示M从初始状态和空栈开始 对于i=0,1,,m-1，有(ri+1,b)∈δ(ri,ωi+1,a)，其中si=at，si+1=bt，a，b∈ε，和t∈* rm∈F

初学者了解知识点，掌握知识点。

作业网址： : #PART 1：如何运行代码 问题 4：Shell 脚本：q4.sh 运行大约需要 20 秒 给定从训练数据产生计数的代码 python count_cfg_freq.py parse_train.dat > cfg.counts --> 生成计数文件 用稀有替换单词并用稀有生成新的训练数据 python add_rare.py cfg.counts parse_train.dat > parse_train_rare.dat --> 将带有稀有的新源文件输出到 parse_train_rare.dat 生成稀有训练数据的计数 python count_cfg_freq.py parse_train_rare.dat > cfg_rare.counts --> 生成新的计数文件 问题 5：Shell 脚本：q5.sh 耗时不到 2 分钟 appllies cky_a

转化上下文文法为push down automata，输入文件识别；第一行为文件数，之后为文法，想转化为pda，然后再判断识别

用到DFA有穷自动机的建立 构建识别活前缀的DFA利用项目集和状态转换函数建立LR(0)分析表 上下文无关文法测试 E->aA E->bB A->cA A->d B->cB B->d #

运行使用jupyter，pycharm均可，基于python3， 算法是由计算导论课本上的证明步骤得来的，欢迎参考留言