版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、1Normal Forms for CFGsEliminating Useless VariablesRemoving EpsilonRemoving Unit ProductionsChomsky Normal Form2Variables That Derive NothingConsider: S - AB, A - aA | a, B - ABAlthough A derives all strings of as, B derives no terminal strings.Why? The only production for B leaves a B in the senten
2、tial form.Thus, S derives nothing, and the language is empty.3Discovery AlgorithmsThere is a family of algorithms that work inductively.They start discovering some facts that are obvious (the basis).They discover more facts from what they already have discovered (induction).Eventually, nothing more
3、can be discovered, and we are done.4Picture of DiscoveryStart withthe basisfactsRound 1:Add factsthat followfrom thebasisRound 2:Add factsthat followfrom round 1and thebasisAnd so on 5Testing Whether a Variable Derives Some Terminal StringBasis: If there is a production A - w, where w has no variabl
4、es, then A derives a terminal string.Induction: If there is a production A - , where consists only of terminals and variables known to derive a terminal string, then A derives a terminal string. 6Testing (2)Eventually, we can find no more variables.An easy induction on the order in which variables a
5、re discovered shows that each one truly derives a terminal string.Conversely, any variable that derives a terminal string will be discovered by this algorithm.7Proof of ConverseThe proof is an induction on the height of the least-height parse tree by which a variable A derives a terminal string.Basi
6、s: Height = 1. Tree looks like:Then the basis of the algorithmtells us that A will be discovered.Aa1an. . .8Induction for ConverseAssume IH for parse trees of height AB | C, A - aA | a, B - bB, C - cBasis: A and C are discovered because of A - a and C - c.Induction: S is discovered because of S - C.
7、Nothing else can be discovered.Result: S - C, A - aA | a, C - c11Unreachable SymbolsAnother way a terminal or variable deserves to be eliminated is if it cannot appear in any derivation from the start symbol.Basis: We can reach S (the start symbol).Induction: if we can reach A, and there is a produc
8、tion A - , then we can reach all symbols of .12Unreachable Symbols (2)Easy inductions in both directions show that when we can discover no more symbols, then we have all and only the symbols that appear in derivations from S.Algorithm: Remove from the grammar all symbols not discovered reachable fro
9、m S and all productions that involve these symbols. 13Eliminating Useless SymbolsA symbol is useful if it appears in some derivation of some terminal string from the start symbol.Otherwise, it is useless.Eliminate all useless symbols by:Eliminate symbols that derive no terminal string.Eliminate unre
10、achable symbols.14Example: Useless Symbols (2)S - AB, A - C, C - c, B - bBIf we eliminated unreachable symbols first, we would find everything is reachable.A, C, and c would never get eliminated.15Why It WorksAfter step (1), every symbol remaining derives some terminal string.After step (2) the only
11、 symbols remaining are all derivable from S.In addition, they still derive a terminal string, because such a derivation can only involve symbols reachable from S.16Epsilon ProductionsWe can almost avoid using productions of the form A - (called -productions ).The problem is that cannot be in the lan
12、guage of any grammar that has no productions.Theorem: If L is a CFL, then L- has a CFG with no -productions.17Nullable SymbolsTo eliminate -productions, we first need to discover the nullable symbols = variables A such that A =* .Basis: If there is a production A - , then A is nullable.Induction: If
13、 there is a production A - , and all symbols of are nullable, then A is nullable.18Example: Nullable SymbolsS - AB, A - aA | , B - bB | ABasis: A is nullable because of A - .Induction: B is nullable because of B - A.Then, S is nullable because of S - AB.19Eliminating -ProductionsKey idea: turn each
14、production A - X1Xn into a family of productions.For each subset of nullable Xs, there is one production with those eliminated from the right side “in advance.”Except, if all Xs are nullable (or the body was empty to begin with), do not make a production with as the right side.20Example: Eliminating
15、 -ProductionsS - ABC, A - aA | , B - bB | , C - A, B, C, and S are all nullable.New grammar:S - ABC | AB | AC | BC | A | B | CA - aA | aB - bB | bNote: C is now useless.Eliminate its productions.21Why it WorksProve that for all variables A:If w and A =*old w, then A =*new w.If A =*new w then w and A
16、 =*old w.Then, letting A be the start symbol proves that L(new) = L(old) .(1) is an induction on the number of steps by which A derives w in the old grammar.22Proof of 1 BasisIf the old derivation is one step, then A - w must be a production.Since w , this production also appears in the new grammar.
17、Thus, A =new w.23Proof of 1 InductionLet A =*old w be a k-step derivation, and assume the IH for derivations of fewer than k steps.Let the first step be A =old X1Xn.Then w can be broken into w = w1wn, where Xi =*old wi, for all i, in fewer than k steps. 24Induction ContinuedBy the IH, if wi , then X
18、i =*new wi.Also, the new grammar has a production with A on the left, and just those Xis on the right such that wi .Note: they all cant be , because w .Follow a use of this production by the derivations Xi =*new wi to show that A derives w in the new grammar.25Unit ProductionsA unit production is on
19、e whose body consists of exactly one variable.These productions can be eliminated.Key idea: If A =* B by a series of unit productions, and B - is a non-unit-production, then add production A - .Then, drop all unit productions.26Unit Productions (2)Find all pairs (A, B) such that A =* B by a sequence
20、 of unit productions only.Basis: Surely (A, A).Induction: If we have found (A, B), and B - C is a unit production, then add (A, C).27Proof That We Find Exactly the Right PairsBy induction on the order in which pairs (A, B) are found, we can show A =* B by unit productions.Conversely, by induction on
21、 the number of steps in the derivation by unit productions of A =* B, we can show that the pair (A, B) is discovered.28Proof The the Unit-Production-Elimination Algorithm WorksBasic idea: there is a leftmost derivation A =*lm w in the new grammar if and only if there is such a derivation in the old.
22、A sequence of unit productions and a non-unit production is collapsed into a single production of the new grammar.29Cleaning Up a GrammarTheorem: if L is a CFL, then there is a CFG for L that has:No useless symbols.No -productions.No unit productions.I.e., every body is either a single terminal or h
23、as length 2.30Cleaning Up (2)Proof: Start with a CFG for L.Perform the following steps in order:Eliminate -productions.Eliminate unit productions.Eliminate variables that derive no terminal string.Eliminate variables not reached from the start symbol.Must be first. Can createunit productions or usel
24、essvariables.31Chomsky Normal FormA CFG is said to be in Chomsky Normal Form if every production is of one of these two forms:A - BC (body is two variables).A - a (body is a single terminal).Theorem: If L is a CFL, then L has a CFG in CNF.32Proof of CNF TheoremStep 1: “Clean” the grammar, so every body is either a single terminal or of length at least 2.Step 2: For each body a single terminal, make the right side all vari
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 第六單元綜合訓(xùn)練教學(xué)設(shè)計-2023-2024學(xué)年語文六年級下冊統(tǒng)編版
- 【教學(xué)能手大賽】統(tǒng)編版語文八上 11 短文二篇-《記承天寺夜游》教學(xué)設(shè)計
- 人教A版(2019)選擇性必修第二冊 5.3.1 函數(shù)的單調(diào)性 教案
- 學(xué)前教育科學(xué)研究的基本概念
- 監(jiān)理工程師《建設(shè)工程監(jiān)理基本理論和相關(guān)法規(guī)》考前模擬真題及答案A卷
- 高中心理健康教育《一寸光陰一寸金-管理學(xué)習(xí)時間》教案
- 17《小猴子下山》教學(xué)設(shè)計
- 古詩詞誦讀《靜女》教學(xué)設(shè)計統(tǒng)編版必修上冊
- 【核心素養(yǎng)目標(biāo)】4.5光的色散 教案 2023-2024學(xué)年人教版八年級物理上冊
- 外研版(2019) 選擇性必修第一冊 Unit 2 Onwards and Upwards Developing ideas教案
- lxh汽輪機TSIe
- 小學(xué)三年級上冊品德道德與法治-《走近我們的老師》(23張)ppt課件
- 最新 育嬰師實操技能題
- 勞務(wù)培訓(xùn)計劃
- 項目部管理人員分工
- (完整版)鋼板焊接施工方案
- (完整版)生產(chǎn)異常問題反饋流程
- 航車安全操作規(guī)程
- 祖國啊我親愛祖國紅色 詩歌朗誦 作品PPT課件
- 2021年掃黑除惡工作計劃
- 天然氣管道置換方案(精)
評論
0/150
提交評論