1

アルファベット：0、1

各文字を反転する反転を考えてみましょう: 0 -> 1; 1 -> 0 したがって、w = 0011 の場合、w-flip = 1100

逆順は逆順の文字であると考えてください。したがって、w = 01101 の場合、w-reverse = 10110 です。

今、私は文字列 w を受け取り、w を印刷する PDA を作成しようとしています (w-flip-reversed)

w = 011
w-flip = 100
w-flip-reverse = 001

したがって、これは次のように出力されます: "011001"

# はブランク文字と見なしてください。したがって、文字列は #011# で始まります

遷移表は次のようになります。

State:    Symbol Read:    Next State:    Head Instruction:
start     #               r1             L

等々

何か案は？

4

1 に答える 1

2

文字列を出力するのは簡単です (願わくば)。0フリップを印刷するのは、読むときに印刷するのと同じくらい簡単で、1その逆も同様です。

反転を開始するための大まかなスケッチ:

  • ひもを 1 つずつ置き、反転できるようにする場所が必要なので、先入れ後出しの保管が理想的です (これは PDA ではどうでしょうか?)。
  • 次に、文字列の末尾を監視して、簡単に反転できるように文字列を保存してから出力に切り替えるタイミングを知る必要があります。
  • 次に、文字列の各部分を正しい逆の順序で取得し (FILO が保存されている場合は簡単です)、それを出力し、文字列の最後に到達したら停止する必要があります。

あなたの場合、反転した文字列を元に戻すために保管する必要があります。

于 2010-11-13T17:52:37.593 に答える