【シプサ】5 帰着可能性 (その8)

こつこつ。

• 「5.2 EQ[CFG]が補Turing認識可能であることを示せ。」
  
  
  
  • いろいろ考えてみた。こういう風にいろいろ考えてみるのはとても訓練になると思う。
    
  • で、EQ[CFG]の補集合が認識可能であることは、認識可能なTMを構成することによってできると思えてきた。
    
  • 大筋を書く。
    
    
    
    • 入力は、<G,H>。
      
    • 入力が不適切なら受理。
      
    • 入力が適切ならば、それらと等価なPDAを構成。両PDAのアルファベットの和集合をΣとする。
      
    • Σ*を生成する装置を構成。
      
    • それをGとHで動作させる。文脈自由文法は判定可能だから、かならずそれぞれ受理か拒否になる。
      
    • GとHとで、受理or拒否が食い違ったなら、受理とする。
      
    • 同じなら、次の文字を試す。
      
    
    
  • これによって、EQ[CFG]の補集合について、判定は不可能だが、認識は可能である。■
    
  
  
  
• 5.3 Post対応問題の具体的な例
  
  
  
  • 上段と下段の文字列長の和が違うのでマッチは存在しない。
    
  • これ、何を意図した問題なのかな???
    
  
  
  
• 「5.4 A <=m BかつBが正規言語ならば、Aは正規言語となるか? その理由を述べよ。」
  
  
  
  • これ、結構考えたが、地味に難しい。。。
    
  
  

次回は、5.4の続きから。