計(jì)算理論基礎(chǔ)教學(xué)大綱-文庫吧資料
2024-09-12 19:14本頁面
【正文】 額外察覺結(jié)束）。 在 Chomsky范式基礎(chǔ)上的動(dòng)態(tài)規(guī)劃算法以及其復(fù)雜度分析。 上下文無關(guān)語言的 泵定理 （ 重點(diǎn) ）。但 上下文無關(guān)語言與正則語言在交下又是封閉的 。 下推自動(dòng)機(jī)和上下無關(guān)文法之間的互化。 ? *下推自動(dòng)機(jī)的相關(guān)定義。 上下文無關(guān)語言與正則語言的關(guān)系 。 ? *有關(guān)有窮自動(dòng)機(jī)的算法及其時(shí)間復(fù)雜度的分析 ： NOTE: 注 *號者為必修內(nèi)容 正 則表達(dá)式－ 非確定型自動(dòng)機(jī)； 確定型自動(dòng)機(jī)－ 正則表達(dá)式； 確定型－ 狀態(tài)最小的確定型； 兩臺(tái)確定型自動(dòng)機(jī)判斷他們的等價(jià)關(guān)系； 兩臺(tái)非確定型自動(dòng)機(jī)判斷他們的等價(jià)關(guān)系； 第三章 上下文無關(guān)語言 ? *上下文無關(guān)文法 ： 上下文無關(guān)文法的相關(guān)定義：規(guī)則，非終結(jié)符，終結(jié)符，它生成的語言等。 （重點(diǎn)） ? *正則語言與非正則語言的區(qū)別 ：泵定理 （重點(diǎn)） ? *狀態(tài)最小化 ：語言等價(jià)類的劃分（它對證明一個(gè)語言是正則語言有什么啟示） 在自動(dòng)機(jī)的基礎(chǔ)上對語言等價(jià)類的劃分以及在原語言的基礎(chǔ)上對語言的劃分 他們之間有什么關(guān)系。
公司管理相關(guān)推薦
鄂ICP備17016276號-1