【シプサ】1 正規言語 (その4)

週明けたら仕事がいそがしい。牛歩戦術じゃないが、こつこつ。

• NFA、というか、非決定性がむずかしい。考え方はわかるのだが、実際に具体的なNFAを構成しようとすると、えらくてこずる。非決定性というのは誰にとっても初めはそういうものなのならよいが、私の頭が悪くてそうだとしたら困るなぁ。Prologとかと関係あるのかな、と期待してがんばってみる。
  
• 1.13にはまった。。。一応解いたが、正解かどうかわからない。というのは、問題文をうまく理解できないからだ。これは日本語力の問題。すなわち求められている言語仕様を理解できているのかどうかがわからない。
  
• 「Fを、{0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在しないような文字列からなる言語とする」
  
• これを日本語として整理すると、
  
  
  
  • {0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在しないような文字列からなる言語
    
  • {0,1}上のすべての文字列のうち、二つの1の間には奇数個の文字が存在することがない文字列からなる言語
    
  • {0,1}上のすべての文字列のうち、「もし二つの1があるならば、それらの間には奇数個の文字が存在することがない」文字列からなる言語
    
  
  
• で、よいのかな?
  
• そうだとするとこれの補集合たる言語の仕様は、
  
  
  
  • {0,1}上のすべての文字列のうち、「二つ以上の1が必ず存在し、それらの1と1の組合せの中には、間に奇数個の文字が存在することが少くとも1つは発生している」文字列からなる言語
    
  
  
• で、よいのかな?
  
• 日本語力の問題でもあるし、論理力の問題でもある。。。
  
• この仕様理解が正しければ、一応解けた。
  
• ちなみに、はじめは補集合たる言語の仕様を
  
  
  
  • {0,1}上のすべての文字列のうち、「二つの1が存在するならば、それらの間には奇数個の文字が存在する」文字列からなる言語
    
  
  
• と考えた。これのNFAが結構難しかったけど、4状態でできた。
  
• でも、それをDFAに変換すると6状態になってしまったのでした。
  

うむー、1.20まで行くつもりだったのだが、、、次回は1.14から。