2。 L=(abi | 0<i<j})とするとき, L(M,)=T(Mi)=L」となる最終状態受理式 DPDA Miを構成せよ. さらに, 構成したM」の遥移図を示せ.【ヒント:aが 入力されるとスタックにXをプッシュする. bが入力されるとスタックからXをポッ するが, スタックのトップがスタック初期記号Z。の場合はポップせずにそのまま し, 最終状態に頂移する. その後はbが入力される限り, 最終状態で遥移を続張 る. 3状態p.qr)で構成可能. 】 3。 =(wefaub}* | 0<れ(w)=導(w), (w)はwに含まれるxの数}とするとき請間 L(M。)=T(M。)=L。となる最終状態受理式DPDA M,を構成せよ. さらに証還 構成したM。の須移図を示せ.【ヒント:aが入力されると最初はスタックにS還還 次からはXをブッシュし, bが入力されるとスタックからSあるいはXをポボップ Sをポップすると最終状態に遥移する. bが多くなるときはTあるいはYをブッンコ する. 2状態p.q!で構成可能. 】 |