Japanese subtitles

← 07-13 Super Hard Quiz Of Doom Solution

Get Embed Code
3 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. 複雑なのでそれぞれ考えてみます
  2. 有限状態機械Aを与えたとします
  3. 点線部分は省略を表します
  4. それが何であれ その有限状態機械について
    言えなければなりません
  5. 少なくとも開始ステートと受理ステートがあります
  6. まず有限状態機械をコピーします
  7. そして最後のステートを
    受理ステートではないように変更します
  8. イプシロン遷移を加えて
    右の開始ステートを消します
  9. 新しい有限状態機械は
    Aでxを受理した部分に相当します
  10. 右側はAの部分でyを受理します
  11. 全体ではx、イプシロン、y
    つまりxyを受理します
  12. 常に成立します
  13. どのような有限状態機械が与えられても
    常にその2倍の大きさの有限状態機械を作り
  14. 与えられた機械で受理されるある文字列を
    つなげたものを受理することができます
  15. 次はもう少し複雑です
  16. ときどき成立するが答えです
  17. 成立する例としない例を出します
  18. 与えられた有限状態機械Bが1つの文字列
    小文字のbだけを受理したとします
  19. 前と同じように考えて
    bbを受理する有限状態機械が作れます
  20. これが言語に含まれる唯一の文字列で
    うまく2倍にしました
  21. 次は成立しない場合を説明します
  22. 上の青い例のBではうまくいきました
  23. そうでないBの例を挙げます
  24. 今度のBはa*xです
  25. 正規表現でのa*xを受理します
  26. 0個以上のaがいくつでも続いたあと
    xが必要です
  27. 前の文とは違うところがあります
  28. こちらは完全に一致した同じ文字列を
    2回繰り返す必要があります
  29. 前の操作と同様の操作で
    この文のとおりの有限状態機械ができたとします
  30. a*xが2回出てくる文字列の例を見ましょう
  31. aがなくてxxとなることがあります
  32. aが1つでaxaxが来る場合もよさそうです
  33. aが2個や3個でもよいでしょう
  34. どうもこのパターンはよくない気がします
  35. 同じ文字列を2回繰り返したものが
    受理できるのであれば
  36. これはa^Nx a^Nxを受理することになります
  37. しかし正規表現では
    a^N b^Nが受理できないようには表せません
  38. 真の例と偽の例を挙げられたので
    ときどき成立すると言えます
  39. 複雑な問題だったので一見して
    分からなかったとしても落ち込まないでください