形式语言自动机-上下文无关文法与下推自动机.ppt

《形式语言自动机-上下文无关文法与下推自动机.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4.3Chomsky范式和Greibach范式Chomsky范式定义：2型文法G＝（N，T，P，S），若生成式形式都是A→BC和A→a，A、B、C∈N，a∈T，则G是Chomsky范式。若ε∈L（G），则S→ε是P的一个生成式，但S不能在任何其它生成式的右边。每个上下文无关文法都具有等效的CNF（定理4.3.1）1CollegeofComputerScience&Technology,BUPTCNF的构成步骤1.用算法1、2、3、4消除ε生成式、无用符号、单生成式2.对生成式A→D1D2…Dnn≥2若Di∈T，则引入新生成式Bi→Di，Bi是新非终结符若Di∈N，则令Bi

2、＝Di，从而将原生成式变化为A→B1B2…Bnn≥2当n>2时，再将其变为A→B1C1，C1→B2C2，C2→B3C3，…，Cn－1→Bn－1BnCi是新引入的非终结符。定理证明――自学2CollegeofComputerScience&Technology,BUPTCNF的构成例例:(书P148例1)设G＝（{A，B，S}，{a，b}，P，S）是无ε、无循环、无无用符号、无单生成式的文法。P：S→aAB∣BAA→BBB∣aB→AS∣b求等效的CNFG1解：∵S→BA，A→a，B→AS,B→b已是CNF∴加入到P1中对S→aAB，将其变换为S→CaC1，Ca→a，C1→AB

3、将A→BBB变换为A→BC2，C2→BB.3CollegeofComputerScience&Technology,BUPTCNF的构成例例:2型文法G＝（{A，B，S}，{a，b}，P，S）P:S→bA∣aBA→bAA∣aS∣aB→aBB∣bS∣b求等效的CNF解：S→CbA∣CaB，增加Cb→b，C2→aA→CbD∣CaS∣a，增加D→AAB→CaE∣CbS∣b，增加E→BB4CollegeofComputerScience&Technology,BUPTGreibach范式Greibach范式(GNF)定义：2型文法G＝（N，T，P，S），若生成式的形式都是A→aβ，

4、A∈N，a∈T，β∈N*，且G不含ε生成式，则称G为Greibach范式，记为GNF。任何2型文法都具有等效的GNF（定理4.3.2）5CollegeofComputerScience&Technology,BUPTGNF的构成步骤1.将2型文法变换为CNF。（A→a，A→BC形式）2.将非终结符排序,再进行代换。对形如Ai→Ajβ（ji）。3.消左递归。对最高的An→Anγ进行变换，使An生成式变为终结符开头。4.回代。将An生成式回代入An－1生成式，使其右部首符为终结符，将An－1生成式回代入An－2生成式，使其右部首符

5、为终结符…5.最后将消直接左递归时引入的A1’、A2’、…An’生成式右部进行代换。使其首符变为终结符。6CollegeofComputerScience&Technology,BUPTGNF的构成例例:(书P149例2)设已有CNF：A→BC，①B→CA∣b，②C→AB∣a，③将其变换为GNF。解:⑴按其非终结符排列为A、B、C，A是低位，C是高位。⑵∵①、②中，右部首符序号高于左部的非终结符∴无需变换。对③，需要变换，将①代入③得C→BCB∣a④，仍需变换，将②代入④得C→CACB∣bCB∣a⑤7CollegeofComputerScience&Technology,B

6、UPTGNF的构成例⑶对上述变换后所得结果消直接左递归对C→CACB∣bCB∣a变换为α1β1β2C→β1∣β2∣β1C’∣β2C’C’→α1∣α1C’即C→bCB∣a∣bCBC’∣aC’⑥C’→ACB∣ACBC’⑦8CollegeofComputerScience&Technology,BUPTGNF的构成例⑷回代将C的生成式⑥回代入B的生成式②B→CA∣b被变换为B→bCBA∣aA∣bCBC’A∣aC’A∣b⑧将新的B生成式⑧回代入A的生成式①A→BC被变换为A→bCBAC∣aAC∣bCBC’AC∣aC’AC∣bC⑨再将新的A生成式⑨代入新引入的C’生成式⑦C’→ACB

7、∣ACBC’被变换为……（略）注意：新引入的Ai’相当于排在最低位。9CollegeofComputerScience&Technology,BUPT§4.4下推自动机（PDA）主要内容PDA的基本概念。PDA的构造举例。用终态接受语言和用空栈接受语言的等价性。PDA是上下文无关语言的接收器。重点PDA的基本定义及其构造PDA与上下文无关语言等价难点根据PDA构造上下文无关文法。10CollegeofComputerScience&Technology,BUPT问题的引出类似于anbn的语言无法由一般的有限自动机识