Return to Video

01-52 Epsilon And Ambiguity

  • 0:00 - 0:03
    Pythonの正規表現モジュールは
  • 0:03 - 0:07
    fsmsimと似ているものを使っています
  • 0:07 - 0:09
    何度もお見せしていますが
  • 0:09 - 0:12
    正規表現を有限状態機械に変換します
  • 0:12 - 0:17
    再帰的な手続きで有限状態機械が
    文字列を受理するかを
  • 0:17 - 0:20
    確認することができます
  • 0:20 - 0:25
    しかしシミュレータはイプシロン遷移と
    あいまいさは処理しません
  • 0:25 - 0:29
    あいまいさの例を出します
    aという2つのエッジのうち
  • 0:29 - 0:32
    受理ステートに行けるのは1つだけです
  • 0:32 - 0:34
    どうするべきでしょう?
  • 0:34 - 0:36
    この例には正式な定義がありますが
  • 0:36 - 0:38
    それでは問題解決しません
  • 0:38 - 0:41
    有限状態機械が文字列sを受理するには
  • 0:41 - 0:46
    開始ステートから受理ステートへとつながる道が
  • 0:46 - 0:49
    1つでもあれば文字列は受理されます
  • 0:49 - 0:52
    これなら受理ステートへ
  • 0:52 - 0:55
    行き着くことができるので
  • 0:55 - 0:57
    aは受理されます
  • 0:57 - 1:00
    有限状態機械は寛容だと言えるかもしれません
  • 1:00 - 1:03
    受理できる遷移が1つでもあればそれでいいのです
  • 1:03 - 1:06
    しかしfsmsimではこれらを
  • 1:06 - 1:08
    コーディングしていませんので
  • 1:08 - 600:00
    この2つの問題を解決する必要があります
Title:
01-52 Epsilon And Ambiguity
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
01:11

Japanese subtitles

Revisions