【形式言語】文脈自由文法を例題を用いて丁寧に解説

基礎理論
スポンサーリンク

 

・文脈自由文法って何??

・例題を用いて分かりやすい説明が欲しい

・急にわからない単語出すのはやめて欲しい

 

今回の記事では、このような文脈自由文法をほとんどわかっていない方に向けて、例題を用いて丁寧に解説していきます。

 

そもそも文法って何?

一言でいえば、「文を生成する規則」のことを文法と言います。ここでいう文法は英語の授業などで習う文法とは厳密性の点で違います。英語のような自然言語には、曖昧性が存在しますが、ここで言う文法には曖昧性がありません。

曖昧性が存在しては、コンピューターが処理することができませんからね。そこで、曖昧性を排除した文法というのは、私たちが知っている文法と違い、厳密な書き方が存在します。

まずは、その書き方を理解していきましょう。結論から言えば、

G=(N, T, P, S) これが文法です。

意味が分からないと思うので、順に確認していきましょう。

 

生成規則(書き換え規則)(P : Production rule)

〇→×

のように表記されるものを生成規則と言います。〇→×は〇を×で置き換え可能という意味です。

たとえば、

数値 → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  (※’|’ は ‘または’ の意味)

のような生成規則が考えられます。これは、’数値’ という記号は0~9のいずれかの数に置き換え可能ということを意味します。

 

終端記号(T : Terminal symbol)

「これ以上置き換え不可能な記号」のことを終端記号と言います。

たとえば、

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9  ( 数値 )

は一般的に、終端記号として存在します。というのも、

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 のような数字は一般的に一番下位の概念であり、これ以上置き換えられるような記号は考えにくいからです。

このように、「これ以上置き換え不可能な記号」のことを終端記号と言います。

また、(a, b, c)など小文字で表記される場合が多いです。

 

非終端記号(N : Non-Terminal symbol)

「置き換え可能な記号」のことを非終端記号と言います。

たとえば、

数値 → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

のような生成規則があるとき、’数値’ という非終端記号は0~9のいずれかの記号置き換え可能ということを意味します。

このように、「置き換え可能な記号」のことを非終端記号と言います。

また、(S, V, W)など大文字で表記される場合が多いです。

 

開始記号(S : Start symbol)

たとえば、

  • S→英文
  • 英文→主語+述語
  • 主語 → 名詞 | 名詞句 | 名詞節
  • 述語 → 動詞 

のような3つの生成規則からなる文法が存在したとします。この場合、’S’という非終端記号「全ての記号を内包できている(最も多くの記号を内包できている)」ことが分かるでしょうか。 

‘主語’ から変形させていけば、’述語’ や ‘英文’ になることはないですが、’S’ を変形させていけば、どの記号であっても変形させることが可能ですよね。

このように「書き換えを開始する最初の非終端記号」のことを開始記号と言います。

 

文法(G : Grammer)

上記で紹介したような、有限集合N, T, P, S の四つ組のことを文法と言い、

G=(N, T, P, S)

と表記します。

例えば、

  • S→英文
  • 英文→主語+述語
  • 主語 → 名詞 | 名詞句 | 名詞節
  • 述語 → 動詞 

という文法であれば、それぞれの有限集合は

  • N = {英文, 主語, 述語, S}
  • T = {名詞 , 名詞句 , 名詞節 , 動詞}
  • P = {英文→主語+述語 , 主語 → 名詞 | 名詞句 | 名詞節 , 述語 → 動詞 }

です。

 

文脈自由文法

いよいよ文脈自由文法の解説です。

簡単に言えば、文脈自由文法とは生成規則の左辺が1字のみである文法のことを指します。

例えば、

A → a+b は文脈自由文法ですが、

AB → a+b+c+d のように「左辺が1字以上である生成規則が含まれる文法」文脈自由文法とは言いません。

 

文脈自由文法以外の文法

文法の種類としては、制限の強さによって以下の4種類に分類することができます。

制限なし文法 < 文脈依存文法 < 文脈自由文法 < 正規文法 

例えば、文脈依存文法であれば、

aXb → aYb 

のような生成規則も存在可能です。これは aXb という文脈においてのみ aYb に置き換え可能であるということを意味しています。

基本・応用情報技術者試験においては、文脈自由文法しか出題されません。

 

例題

それでは、例題を用いて理解できているか確認しましょう。

 

$Q$ : 以下の生成規則の中で、文脈自由文法の生成規則となりうるものを全て選べ

  1.  aXb → aYb
  2.  S→GoldenDatabase
  3.  式→式+項
  4.  数式→数字+記号
  5.  AcA→acaa 

 

$A$

「左辺が非終端記号1つの生成規則」のみが文脈自由文法の生成規則としてふさわしいので、➁ , ➂ , ➃ が正解です。

 

まとめ

基本・応用情報技術者試験に出てくる問題は大体文脈自由文法です。しっかり意味を押さえておきましょう。

コメント

タイトルとURLをコピーしました