基本情報技術者試験(FE) ~情報の基礎理論「形式言語・数式記法」~ 【第1回】


情報の基礎理論

 

形式言語・数式記法 その1

 

オートマトン

 
「オートマトン」とは、コンピュータの動作を数学的な観点からモデル化したもので、「入力」に対し、「状態」を変化させて処理を行い、「停止」することで結果を出力するといった、仮想的な機械の概念を示します。特に入力と状態の個数が有限個からなるオートマトンを「有限オートマトン」といいます。
「有限オートマトン」は、以下のような点を表または図で示します。

  • 入力に対する状態変化を「状態遷移表」、「状態遷移図」で示す。
  • 入力の開始位置は、初期状態(→で示す位置)から始まる。
  • 入力に対する正常終了(これを「受理された」と呼ぶ)は、必ず受理状態で終わる必要があります。◎で示す。

 
kihon04-01
 
次の図の「有限オートマトン」で、入力値として「10111」を入力した場合、「S0 → S1 → S0  → S1 → S3 → S2」と遷移するため、正常に受理されます。
一方、「11110」と入力した場合、「S0 → S1 → S3 → S2 → S4 → S4」と遷移するため、正常に受理されないことになります。
 
kihon04-02
 

形式言語(正規表現)

 
私たちが日常的に使用する自然言語は、ある形式に従って言葉を作り、話す・記述することを行っていますが、その使用方法には多様性があり、形式を明確に定義することは困難です。
一方、コンピュータで使用する言語は、明確な定義のもとで作成した形式(フォーマット)に従い、文字やプログラムを読み、理解します。これを「形式言語」といいます。「形式言語」の代表的な表記として、「正規表現」、「BNF」などがあります。

「正規表現」は、文字列などの記号列を表現する形式言語です。「正規表現」では、有限個の記号に対して、規則を表す「メタ文字」を組み合わせて表現します。
 

メタ文字 意味
[A-Z] 英文字1文字を表す。
直前の正規表現の0回以上の繰返し。
+ 直前の正規表現の1回以上の繰返し。
? 直前の正規表現の0個または1個あることを表す。
左右にある正規表現のいずれかを表す。

 
例えば、「[A-Z]+[0-9]*」は、「A」「ABC」「WINDOWS7」「LINUX」などが該当しますが、「20130401」などの文字列は該当しません。
 

ページ:

1

2
  • このエントリーをはてなブックマークに追加

PAGE TOP