【シプサ】2 文脈自由言語 (その5)

こつこつ。

• 文脈自由言語の演習もやはり重い。ひとつひとつでてきた言語を吟味せねばならんから、しかたない。
  
• 2.4。問題文の「列」の使い方がおかしいような。この言語は、解答から考えるに、「wは少なくとも三つの1を部分文字列として含む」じゃないかなぁ。しかしCFGは強力だ。
  
• 2.5。PDAも強力。NFAとくらべると記述力が高い。
  
• 2.6。CFGを考えるのが結構大変。
  
• 2.7。2.6のPDA。PDAの方がかなり簡単に構築できる。
  

4問で6時間くらいつかってしまった。しかたなし。