情報処理のWeb教科書―IPA情報処理試験対策のお供に!

情報に関する理論―形式言語と有限オートマトンの状態遷移図など

トップ 情報処理の知識体系 テクノロジ系 基礎理論 情報に関する理論

情報に関する理論として、形式言語と有限オートマトンの状態遷移図などの解説や演習問題をまとめています。

目次

以下は目次リンクになります。

2. 符号理論

3. 文字の表現

5. 形式言語

6. オートマトン

9. AI

10. コンパイラ理論

もっと知識を広げるための参考

更新履歴

2. 符号理論

符号理論について見ていきます。

ハフマン方式

ハフマン方式は、発生確率が分かっている記号群を符号化したとき、1記号当たりの平均符号長が最小になるように割り当てる方式です。

符号理論に関連したIPA情報処理試験の過去問

以下では符号理論に関連したIPA情報処理試験の過去問とそのの解説をまとめています。

3. 文字の表現

文字コードについて見ていきます。

文字符号化方式

文字符号化方式とは、読み方は「もじふごうかほうしき」。 英語で「character encoding scheme」、略して「CES」といいます。 文字とそれに割り振られた数値の対応をまとめたコード化体系のことです。 省略して符号化方式という場合もあります。

ASCIIコード

ASCIIコードとは、大文字小文字のアルファベット・数字・記号類・制御コードを7ビットで表現する文字コードです。

EUC

EUCとは、Extended UNIX Codeの略で、拡張UNIXコードといわれる文字コードです。 複数のバイト幅を用いて漢字のような膨大な数の文字でも扱うことができるようになっている文字コードです。

JISコード

JISコードとは、Japan industrial standardsの略で、ISOコードに片かなを考慮して日本で制定したコードです。 1バイト系(JIS X 0201)は7ビットの7単位コードと片かなも組み込んだ8ビットの8単位コードがあります。

JISコードの例

二つの文字“A”と“2”をこの順にJISコードで表すと次のようになります。

JISコードの例

2つの文字“A”と“2”をこの順にJISコードで表したものは、「01000001  00110010」になります。

シフトJISコード

JISコードとは、文字の1バイト目を見るだけで漢字か半角英数字かわかる文字コードです。

Unicode

Unicodeとは、すべての文字を16ビット(2バイト)で表現し、1つの文字コード体系で多国語処理を可能にしようとする文字コードです。

UCS-2

UCS-2とは、Universal multi-octet Character Set 2の略で、ISO/IEC 10646(JIS X 0221)のBMP(Basic Multilingual Plane:基本多言語面)として採用され、1文字を2バイトで表現する文字コードです。

文字の表現に関連したIPA情報処理試験の過去問

以下では文字の表現に関連したIPA情報処理試験の過去問とそのの解説をまとめています。

5. 形式言語

形式言語は、プログラミング言語のように特定の目的のために意図的に作られた言語のことを言います。

BNF

リンク先にBNFとはどのような記法かをまとめています。情報処理のBNFとはどんなものか理解したい、意味はもちろん、記法例や問題つきで解説されていると助かるという方におすすめのコンテンツです。

詳細

逆ポーランド記法

逆ポーランド記法について見ていきます。

ポーランド記法

ポーランド記法とは、演算子をそのオペランドの前(または後)に置く表記法をいいます。 演算子を後におく記法を逆ポーランド記法ともいいますが、単にポーランド記法ということも多いようです。 たとえば、「a+b」は「ab+」となります。

ポーランド記法は、評価の容易さと括弧などの区切りを用いずに式を一意的に表記できることなどから、言語プロセッサで利用されています。

逆ポーランド記法

逆ポーランド表記法とは、ポーランド記法の後置表記法のことを言います。

逆ポーランド記法は、演算子を演算対象の後ろに記述する記法です。 たとえば、「A+B*C」という式の場合「ABC*+」というように、あるいは式Y=(A-B)×CをYAB-CX=と表記します。

逆ポーランド記法の例

ここでは、Y=(A+B)×(C-(D÷E))をポーランド記法で表してみる場合を考えます。 この場合、以下のように木で表現し、節から上に出るときにそこの記号を書いていくと便利です。

木を使ってポーランド記法に直す

最後に「Y=」の部分を加えると以下が導かれます。

YAB+CDE÷-×=

逆ポーランド記法に関連したIPA情報処理試験の過去問

以下では逆ポーランド記法に関連したIPA情報処理試験の過去問とそのの解説をまとめています。

6. オートマトン

有限オートマトンの概念や状態遷移表、状態遷移図についてまとめていきます。

有限オートマトンとは

有限オートマトンとは、入力テープの記号を1つ読んでは、状態遷移表や状態遷移図に示されるモデルに従って状態を遷移します。

状態遷移図と状態遷移表

状態遷移図とは、状態の移り変わりを図で表したものです。 時間の経過や事象の発生に基づいて記述していきます。 なお、以下のように表形式で表す場合もあります。

文字列
空白数字符号小数点その他
 現 
 在 
 の 
 状 
 態 
 a 
 b 
 c 
 d 
 a 
 a 
 e 
 a 
 b 
 b 
 b 
 e 
 c 
 e 
 e 
 e 
 d 
 d 
 d 
 e 
 e 
 e 
 e 
 e 

有限オートマトンの状態遷移図の読み方

有限オートマトンの状態遷移図の読み方は、簡単です。

例えば、S1は初期状態を、S3は受理状態を表している場合に次に示す有限オートマトンが受理する入力例は1101になります。

【問3】有限オートマトン―平成21年春期応用情報技術者

S1⇒S2⇒S1⇒S3⇒S3

有限オートマトンの状態遷移表の読み方

例えば、以下の有限オートマトンの状態遷移図で110の入力をaから始めると、aが1の入力の場合、aの行の1の列にあるbに遷移します。

有限オートマトンの状態遷移表ー読み方1
01
aab
bcd
cab
dcd

そして、次の入力が1でbの行の1の列にあるdに遷移します。

有限オートマトンの状態遷移表ー読み方2
01
aab
bcd
cab
dcd

最後の入力は0でdの行の0の列にあるcに遷移します。

有限オートマトンの状態遷移表ー読み方3
01
aab
bcd
cab
dcd

最後にcになりました。aから始めましたが、b、c、dどこから始めても110の入力の場合cになります。

オートマトンに関連したIPA情報処理試験の過去問

以下ではオートマトンに関連したIPA情報処理試験の過去問とそのの解説をまとめています。

9. AI

AIとはをテーマに、AI(人工知能)の基本的な考え方、機械学習のwakeなど関連知識について見ていきます。

詳細

10. コンパイラ理論

コンパイラとは何か、コンパイラ理論、コンパイラによる最適化の仕組みついてまとめています。 無料でダウンロードできるc言語のコンパイラの紹介やコンパイラ言語とインタプリタ言語の違いなどをまとめています。

詳細

もっと知識を広げるための参考

更新履歴

更新履歴になります。

戻る

スポンサーリンク

情報処理の知識体系

プログラミング

各試験の問題と解説

ランダム出題・採点アプリ

スポンサーリンク