計(jì)算理論基礎(chǔ)教學(xué)大綱(編輯修改稿)
2024-10-10 19:14 本頁面
【文章內(nèi)容簡介】 上下文無關(guān)文法 ： 上下文無關(guān)文法的相關(guān)定義：規(guī)則，非終結(jié)符，終結(jié)符，它生成的語言等。 還有其上的推導(dǎo)。 上下文無關(guān)語言與正則語言的關(guān)系 。 語法分析樹，推導(dǎo)之間的“ 先于 ”關(guān)系，最左，最右推導(dǎo)； 歧義性的定義 。 ? *下推自動(dòng)機(jī)的相關(guān)定義。 ? *下推自動(dòng)機(jī)與上下無關(guān)語言的關(guān)系。 下推自動(dòng)機(jī)和上下無關(guān)文法之間的互化。（ 重點(diǎn) ） ? *上下文無關(guān)語言與非上下文無關(guān)語言 上下文無關(guān)語言在并，連接和 Kleene運(yùn)算下的封閉性，和它為什么 在補(bǔ)和交下不封閉。但 上下文無關(guān)語言與正則語言在交下又是封閉的 。 單文字的上下文無關(guān)語言必定是正則語言。 上下文無關(guān)語言的 泵定理 （ 重點(diǎn) ）。 ? *關(guān)于上下文無關(guān)文法的算法 上下文無關(guān)文法－ 等價(jià)的下推自動(dòng)機(jī)； 下推自動(dòng)機(jī)－ 等價(jià)的上下文無關(guān)文法； 給定一上下文無關(guān)文法 G和一字符串 w,判定 w?L(G). Chomsky 范式 ，將任一上下文無關(guān)文法化為等價(jià)的 Chomsky范式。 在 Chomsky范式基礎(chǔ)上的動(dòng)態(tài)規(guī)劃算法以及其復(fù)雜度分析。 ? 確定性與語法分析 下推自動(dòng)機(jī)的確定型定義，字符串之間的相
公司管理相關(guān)推薦
鄂ICP備17016276號-1