応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

1.基礎理論 > 1.6 形式言語

オートマトンとは、状態遷移図のモデルです。
たとえばタスク管理において、「実行状態」「実行可能状態」「待ち状態」の3つの状態を遷移します。
過去問(H20FE秋午前問29)では、コンピュータのタスクの状態遷移として、次の図が記載されています。
状態遷移
また、実行状態のタスクが、「自分より優先度の高いタスクが実行可能状態になった」ことで、実行可能状態に遷移するともあります。

このように、ある「状態」と「遷移」の様子を表したモデルがオートマトンです。かつ、状態や遷移が有限なものが有限オートマントンです。

実際の過去問(H21春AP午前問3)の有限オートマトンを見てみましょう。問題文には、「S1は初期状態を,S3は受理状態を表している。」とも記載があります。
automaton
ここで、初期状態のS1に1が与えられるとS2に遷移し、0が与えられるとS3に遷移します。
S2においては、0が与えられるとS2のままで、1が与えられるとS1に遷移します。
S3においては、0が与えられるとS2に遷移し、1が与えられるとS3のままです。

過去問を見てみよう!
■H28秋AP午前
問4 表は,入力記号の集合が{0,   1},状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
manton
ア a   イ b   ウ c   エ d
さて、よくわからない問題だと感じた人も多かったことでしょう。状態集合が{a, b, c, d}であり、それに対して入力記号の集合が{0,   1}です。問題文の状態遷移表をオートマトンの図にすると、以下になります。
auto 
ここで、最後が110で終わっているものを受理すると、樹里状態はa〜dのどれになるのでしょうか。というのが問題です。最後が110というのがよく分かりませんが、とにかく、a〜dの4つの中のいずれかからスタートしますので、順番に入れてみます。

・aからスタート
 a→1→b→1→d→0→c
・bからスタート
 b→1→d→1→d→0→c
・cからスタート
 c→1→b→1→d→0→c
・dからスタート
 d→1→d→1→d→0→c

このように、どこからスタートしても110を受理すると、cで受理状態になります。
正解は、cですからウです。


■H26春
問4 表は,入力記号の集合が{0,1},状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
H26h-4
ア a   イ b   ウ c   エ d
【正解】ウ

■H25春
問3 図は,偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり,二重丸が受理状態を表す。 a,bの適切な組合せはどれか。
H25h-3_1図
H25h-3_2選択肢表
【正解】ウ

まずは過去問(H24秋AP午前問4)を見てみましょう。
問4 式 E=(A+B)×(C−D)と対応する逆ポーランド表記法はどれか。
ア =EX+AB−CD ウ EAB−CD+×=
イ EAB+CD−×= 工 EABCX+D−=

逆ポーランド表記法は、パッと見は難しいのですが、方式を覚えて慣れてしまえば難しくはありません。後述する過去問(H25春AP午後問2)をベースに解説します。
まず、表記の方法は、 2×3 を 23× とします。演算子を演算対象のすぐ後ろに配置するのです。このルールだけ覚えてください。
では、 1+2×3 はどうなるかというと、(2×3)をZと考えると、1+Zですから、1Z+になります。Zに23×を入れると、123×+となります。
2
よって、この問題の正解はイです。
応用情報技術者試験を勉強する成子 

なぜこんな面倒なことをするのですか?
先ほどの過去問には、「逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。」とあります。

上記の過去問ですが、このルールに従うと、 A+B は AB+ 、 C−D は CD− 
(A+B)と(C−D)をそれぞれの塊とみた上で掛け算をするので、 (A+B)×(C−D) は AB+CD−× になります。この塊とEを「=」という演算をすると考えればいいので、 EAB+CD−×= が正解です。
 
さて、過去問(H25春AP午後問2)に、逆ポーランド表記法に関する出題があるので以下に掲載します。
問2 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムに関する次の記述を読んで,設問1〜3に答えよ。
 逆ポーランド表記法とは,演算子を二つの演算対象の後ろに配置することによって,数式を表現する表記法である。例えば,一般的な表記法の数式1+2×3を,逆ポーランド表記法では123×+と表記する。
 逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。
 一般的な表記法の数式から逆ポーランド表記法への変換は,スタックを用いることで容易に実現できる。

〔逆ポーランド表記法への変換アルゴリズム〕
 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムでは,まず変換前の数式を,数値,演算子及び括弧の要素(以下,演算要素という)に分解する。
演算子には二項演算子十,−,×,÷を用い,括弧には"("と")"を用いる。
数値は0〜9の1桁の数とする。それぞれの演算要素には,優先度を定義する。
 変換の処理には,変換前配列,スタック及び変換後配列を用いる。初期状態では,変換前配列には変換前の数式の演算要素が順に入っており,スタックと変換後配列は空の状態である。変換後には,変換後配列に逆ポーランド表記法に変換した結果が入る。例えば,変換前の数式が1+2×3の場合,初期状態は表1のようになる。
a

 逆ポーランド表記法への変換は,次の(1)〜(4)の手順で行う。
(1)変換前配列の先頭から順に,演算要素を1個参照する。
  参照する演算要素がない場合は(4)に進む。
(2)スタック上に演算要素がある場合は,スタックの先頭にある演算要素の優先度を参照し, (1)の演算要素の優先度以上なら,スタックの先頭の演算要素をホップし,変換後配列の末尾に追加する。これを,スタックの先頭の演算要素の優先度が, (1)の演算要素の優先度未満になるまで繰り返す。ただし,スタックの先頭の演算要素が“(”の場合は,そこで繰返しを終了する。
(3)(1)で参照した演算要素が“)”なら,それを破棄し,その際スタックの先頭にあるはずの“(”もホップして破棄した後(1)に戻る。(1)で参照した演算要素が“)”以外なら,その演算要素をスタックにプッシュし. (1)に戻る。
(4)スタック上にある全ての演算要素を順番にホップし,変換後配列の末尾に追加する。

演算要素の優先度を表2に,数式1+2×3を変換するときの処理過程を図1に示す。
なお,図1中の丸で囲った演算要素は, (1)の手順で参照した演算要素である。
b
(後半略)

設問1 逆ポーランド表記法への変換について, (1), (2)に答えよ。
(1)数式(2+3)×4を逆ポーランド表記法に変換した結果を答えよ。
(2)表2及び表4中の[ ア ]〜[ エ ]に入れる適切な二項演算子を、+,−,×,÷の中から一つずつ選んで,表を完成させよ。

(後半略)


過去問を見てみよう!
H28秋AP午前
問3 逆ポーランド表記法で表された式を評価する場合,途中の結果を格納するためのスタックを用意し,式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき,入力が演算子となった。このときに行われる演算はどれか。ここで,演算は中置表記法で記述するものとする。
enzan
ア A 演算子 B   ウ C 演算子 D
イ B 演算子 A   エ D 演算子 C
中置表記法なので、3+4のように、演算子(×や+)が文字と文字の中に入ります。
ちなみに、逆ポーランド記法は、34+などと表記するので、後置記法と言われます。
スタックの流れは以下です。
http://sm.seeeko.com/archives/65909425.html
 (詳しくは別途解説)
スタックは後入れ先出し法(LIFO)ですので、上から順に処理をします。
ただこのとき、リンクの図を見てもらうとわかるように、最初に演算する数値が下に来ます。よって、正解は、ウの C 演算子 D  です。

バッカスナウアーフォームと読みます。
我々が日常で話す言葉が自然言語ですが、そのコンピュータに理解しろというのは無理があります。そこで、ルール(形式)に基づいた言語を形式言語と言います。その代表がBNFです。

BNFでは、2つのルールだけ覚えましょう。

➀ ::= ⇒ 定義する
◆|   ⇒ または

では、例を見ましょう。
bnf
上記のルールに従うと、<digit>には数字の0か1か2か3が入ります。

過去問を見てみよう!
■H29秋
問2 次のBNFにおいて非終端記号〈A〉から生成される文字列はどれか。
〈R0〉::=0|3|6|9
〈R1〉::=1|4|7
〈R2〉::=2|5|8
〈A〉 ::=〈R0〉|〈A〉〈R)〉|〈B〉〈R2〉|〈C〉〈R1〉
〈B〉 ::=〈R1〉|〈A〉〈R1〉|〈B〉〈R0〉|〈C〉〈R2〉
〈C〉 ::=〈R2〉|〈A〉〈R2〉|〈B〉〈R1〉|〈C〉〈R0〉
ア 123   イ 124   ウ 127   エ 128
【正解】ア

■平成29年春期 午前
問4 あるプログラム言語において,識別子(identifier)は,先頭が英字で始まり,それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき,aに入るものはどれか。

bnf
正解は、エです。

1行目から順に解説します。
・<digit>の右に::=がありますので、<digit>という言葉を定義しています。具体的な定義内容は右側にあり、|で区切られているので、0または1または2または・・・9のいずれかの値を取ります。つまり、<digit>は任意の1桁の数字が入ることがわかります。
 ・同様に、<letter>には大文字小文字を含めた任意のアルファベット1文字が入ります。
 ・<identifier>は、<letter>または <identifier><digit>または<identifier><letter>です。順に説明します。
<letter>の場合
任意のアルファベット1文字が入ります。
<identifier><digit>の場合
<identifier>が取りうる値+任意の数字1文字が入ります。
<identifier><letter>の場合
<identifier>が取りうる値+任意のアルファベット1文字が入ります。
,遼‖Г砲靴燭うと、<identifier>は例えばA、△遼‖Г砲靴燭うと、<identifier>は例えばA1、の法則にしたがうと、<identifier>は例えばA1Bです。さらに、この値をもって△筬の法則に当てはめると、たとえばA1B2、A1BC、となります。ここに挙げた5個のいずれの場合でも、<identifier>は先頭が英字で始まり,それ以降に任意個の英数字が続く文字列となります。

このページのトップヘ