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

こつこつ。「1.2 非決定性」から。

• NFAの定義を理解した。
  
• NFAとDFAが等価であることを理解した。
  
• 正規言語のクラスが正規演算(和集合演算・連結演算・スター演算)について閉包であることを理解した。
  
• クラスがある演算に対して閉包ということは、その演算の安全性が保証されることに加えて、そのクラスのそもそもの構造がうかがい知れるんだな。
  
• 正規演算を表現する記法として、正規表現を導入する。これは言語を値とする演算である。
  
• 「言語は、ある正規表現で記述されるとき、かつそのときに限り正規である。」
  
• GNFAの定義を理解した。ただし、GNFAが「いくつかの文字を一つのブロックとして入力から読み出す」というところがわからない。「いくつか」って、いくつなの? とりあえずスルー。
  
• ポンピング補題がなんとなくわかった。
  

これで一章を読んだ。明日は演習をやるぞ。