スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

プログラム化して考えると理解が進む

 一見難しく見える概念も、プログラミングに慣れている人は、実装してみると簡単だと感じることが多いようです。おそらく、他の人もやっていると思うのですが、私は何かの概念を学ぶとき頭の中で実装してみます。例として、先日の日記で書いた有限オートマトンを題材にします。
 私は本来実在するプログラミング言語を使わず、頭の中で処理をするのですが、実際に試せないと読者は面白くないと思います。そこで、有限オートマトンを極力C#の特有機能を使わずに、簡潔に実装してみました。

using System;
using System.Collections.Generic;

//有限オートマトン( FA : finite automaton )
class Fa
{
    //FAの定義に必要なフィールド
    private IEnumerable<string> _stateSet;
    private IEnumerable<string> _inputSet;
    private Func<string, string, string> _stateTransition;
    private string _firstState;
    private IEnumerable<string> _lastStateSet;

    //現在の状態を覚えておく必要がある
    private string _currentState;

    //受理
    public bool IsAccept
    {
        get 
        {
            return this.CheckSet( this._lastStateSet, this._currentState );
        }
    }

    //FAの定義( Q, Σ, δ, q0, F )でインスタンスを生成する
    public Fa(
        IEnumerable<string> stateSet,
        IEnumerable<string> inputSet,
        Func<string, string, string> stateTransition,
        string firstState,
        IEnumerable<string> lastStateSet )
    {
        this._stateSet = stateSet;
        this._inputSet = inputSet;
        this._stateTransition = stateTransition;
        this._firstState = firstState;
        this._lastStateSet = lastStateSet;

        this._currentState = firstState;
    }

    //特定の集合に記号が存在するかチェックする
    private bool CheckSet( IEnumerable<string> set, string target )
    {
        foreach ( string elsement in set ) {
            if ( elsement == target ) {
                return true;
            }
        }
        return false;
    }

    //記号1つを指定して現在の状態を遷移させる
    public bool StateTransition( string input )
    {
        if ( ! this.CheckSet( this._inputSet, input ) )
            throw new ArgumentException( input + "は想定外です" );
        this._currentState =
            this._stateTransition( this._currentState, input );
        return this.IsAccept;
    }
}

class Sample
{
    static void Main()
    {
        //自動販売機の有限オートマトンを用意する
        Fa obj = Init();

        //100円投入してみる
        string input = "100";
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}", 
            input, obj.StateTransition( input ) );

        //もう100円投入
        input = "100";
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

        //投入したふりをしてみる
        input = "0";
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );

        //もう100円を投入
        input = "100";
        Console.WriteLine( "{0}円投入しました。商品は出てきた?{1}",
            input, obj.StateTransition( input ) );
    }

    static Fa Init()
    {
        //機械が取りうる状態
        var state = new string[ ] { "q0", "q100", "q200", "q300" };

        //入力できる記号
        var input = new string[ ] { "0", "100" };

        //状態遷移関数
        Func<string, string, string> stateF =
            ( string x, string y ) => {
                switch ( x ) {
                    case "q0":
                        if ( y == "0" ) return "q0";
                        else if ( y == "100" ) return "q100";
                        break;
                    case "q100":
                        if ( y == "0" ) return "q100";
                        else if ( y == "100" ) return "q200";
                        break;
                    case "q200":
                        if ( y == "0" ) return "q200";
                        else if ( y == "100" ) return "q300";
                        break;
                    case "q300":
                        return "q0";
                }
                throw new ArgumentException( 
                    "指定された状態と入力の組み合わせはあり得ません。" );
            };

        //最終状態
        var last = new string[ ] { "q300" };

        //作成( FA = { Q, Σ, δ, q0, F } )
        return new Fa( state, input, stateF, "q0", last);
    }
}

見ての通りこのプログラムは雑です。C#を使うのであれば、本来はLINQを使用するべきですし、オブジェクト指向で考えるのであれば、これは悪いプログラムです。しかし、概念をちょっとつかむ程度ならば、こんな雑なプログラムの方が役に立ちます。実装に懲りすぎると、必要以上に概念が難しく感じてしまいます。
 この様にプログラム化してみれば、有限オートマトンが言いたいことはすぐにわかりますし、何が問題となるのか、型理論と組み合わせるとどうなるか、・・・など発展事項も自分で探求することができます。
 さて、有限オートマトンは何を表わしているのでしょうか?それは、このプログラムを見れば明らかです。機械の性質は、「状態」「入力記号」「状態遷移方法」「初期状態」「最終状態」の情報を元に、状態を遷移させることにより、与えられた情報が正しいか判定できる事である。むろん、このほかの事もプログラムを触れば出てきます。
 私はさらに、有限オートマトンの発展版である、ミーリー型機械、ムーア型機械、非決定オートマトンなども実装して色々遊びました。そうするうちに、一見難しいオートマトン・言語理論も大半理解することができました。この様にしてプログラム化して考えると、難しいこともわかりやすくなるので、皆様も是非お試しください。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。