search

kkdai / blog

This is blog comment repo for https://www.evanlin.com/
0 stars 0 forks source link

moocs-coursera-automata-note4/ #65

Open kkdai opened 3 years ago

kkdai commented 3 years ago

[Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages

http://www.evanlin.com/moocs-coursera-automata-note4/

kkdai commented 3 years ago

comment written by Hiko Hong, created at 10 Oct 15 16:30 UTC,

哇塞！顧小孩兼上automata!!!! 強者！

kkdai commented 3 years ago

comment written by Dboy Liao, created at 18 Oct 15 06:45 UTC,

我反覆一直看影片~
一直納悶說老師現在在說的是 nondeterministic pda 還是 deterministic?
雖然從分析的對象是 CFG 來看~
應該是 nondeterministic ~
但是我覺得他沒有把 transition function of nondeterministic pda 說清楚~
所以最好看一下這邊:
http://www.seas.upenn.edu/~...

這樣對證明會更有感覺~
不然我怎麼看他的證明總有似是而非的感覺~

kkdai commented 3 years ago

comment written by Dboy Liao, created at 18 Oct 15 06:49 UTC,

我更討厭的是~
理論上 transition function 應該要對所有 state 跟 input 都有定義~
但是他都不講沒明確定義到的 transition 應該怎麼做~
害我卡好久最後才發現是定義問題....Orz
看別人 + wiki 的定義才清楚了一些~
全部寫到筆記裡~
20 分鐘的影片我看了快 2 小時....OrzOrz

kkdai commented 3 years ago

comment written by Evan Lin, created at 19 Oct 15 03:41 UTC,

做到比較後面的章節，會發現TM 的transition function 很多都故意不定義（有可能是因為走不到)．

這個禮拜我會寫個TM的程式出來，可以再討論看看..

kkdai commented 3 years ago

comment written by Dboy Liao, created at 19 Oct 15 16:53 UTC,

不不不~
你看我貼的網址~
它有說沒特別寫出來的 transition rule 都是送到空集合~
也就是沒法兒做任何事~
只能一直輸入空字串~

這樣的好處是能清楚做判定~
譬如說 (f, alpha) 絕對不會在空集合裡~
所以如果一個 state 輸入空字串後進入 f ~
不管 stack 裡有啥~
(f, alpha) 都不會在空集合裡~ (不 accept)
這樣可以明確定義什麼叫 accept ~

kkdai commented 3 years ago

comment written by Simon Niu, created at 21 Apr 18 12:02 UTC,

You save my midterm exam! Thanks!