2

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-twoli1.html#30007-23021r2.2.4から：

M = <Q、Σ、Δ、δ、q 0、F>を決定論的有限状態トランスデューサとし、その遷移図を図2.E.2に示します。

図2.E.2

次の関係のそれぞれについて、関係を計算する有限状態トランスデューサを見つけます。

a。{（x、y）| xはL（M）にあり、yはΔ*}にあります。
b。{（x、y）| xはL（M）にあり、yはΔ*にあり、（x、y）はR（M）にありません}。

はい、これはHWですが、私はこれらの質問に苦労しており、少なくともポインターを使用できます。独自のcを作成したい場合。および/またはd。の答えに私を導くのではなく、それを行う方法を私に示すための例。およびb。それなら明らかに私はそれで大丈夫です。

前もって感謝します！

4

1 に答える 1

2

これまでにどのような進展があったかを示していないので、まったく進展がなかったと想定し、この種の問題にどのように取り組むことができるかについての全体的なガイダンスを提供します。

  • まず、遷移図を調べます。すべての表記の意味を理解していますか？トランスデューサは決定論的として記述されていることに注意してください。それが何を意味するのか分かりますか？遷移図に示されているトランスデューサーは、実際には決定論的であることを確信してください。それをトレースします。どの入力がトランスデューサーによって受け入れられ、どの出力がトランスデューサーに与えられるかを理解するようにしてください。
  • 次に、質問がそれらを参照しているので、このトランスデューサーのL（M）、Δ、およびR（M）が何であるかを理解します。それらの表記が何を意味するか知っていますか？
  • トランスデューサーが特定の関係を計算することの意味を知っていますか？{（x、y）|を理解していますか ...}関係を説明するための表記法？
  • 遷移図を変更して、ε/ 0遷移を削除し、隣接する遷移にマージできますか（1つの遷移で複数のシンボルが出力される可能性があります）。（これは、IMHOが、同じ入力言語を受け入れる他のトランスデューサーを作成するのに役立ちます。この場合、パートaよりもパートbの方が役立ちます。）
  • 元のトランスデューサーとは独立した方法で、作成する必要のあるトランスデューサーを自分で説明してください。これらのトランスデューサーは決定論的ですか？
  • これらのトランスデューサーの遷移図を作成します。
于 2012-03-04T04:43:53.330 に答える