忍者ブログ
 

句構造文法の階層

文法G
非終端記号の集合VN、終端記号の集合VT、書換え規則の集合P、最初に書換え規則が適応される非終端記号σの4項組

VN, VT, P, σ> で定義される。

句構造文法における文の生成は、まず開始記号σを左辺に持つ書換え規則を使って、その記号σを書換え規則の右辺に書換え、新しくできた非終端記号を左辺に持つ書換え規則で、その非終端記号を書換え規則の右辺に書換え……ということを非終端記号が無くなるまで繰り返し行われる。

文法Gによって生成される文の集合L(G)を、文法Gによって生成される言語と呼ぶ。

書換え規則につけられる制限によって、句構造文法は次の4つの型に分けられる。

0型文法 書換え規則に制限がない文法
1型文法 文脈依存文法
       書換え規則に |α| ≦ |β| という制限をつけた文法
2型文法 文脈自由文法
       A → β (AVN, β ∈ (VNVT)+)という形をした書換え規則だけをもつ文法
3型文法 正規文法
       AaB (A, BVN, aVT)、または Aa (AVN, aVT)という形をした書換え規則だけを持つ文法


これらの文法から生成される言語をそれぞれ、0型言語、1型言語、2型言語、3型言語と呼び、その包含関係は、3型言語 ⊂ 2型言語 ⊂ 1型言語 ⊂ 0型言語、となっている。

PR
この記事にコメントする
お名前
メールアドレス
URL
コメント
この記事へのトラックバック
この記事にトラックバックする:
カレンダー
02 2017/03 04
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 15 16 17 18
19 20 22 23 24 25
26 27 28 29 30 31
最新トラックバック
メール
ブログ作成者(はやし)に直接訴えたいことがある、という場合は、下のアドレスにメールをどうぞ。

thayashi#ucalgary.ca
(#を@に置換してください)

ブログ内検索
Google
WWW を検索 このブログ内を検索

はやしのブログ内で紹介された
 書籍の検索はこちら
 音盤の検索はこちら
ランダムおすすめ
(忍者ブログに引越してから、うまくうごかなくなってしまいました。いつか、直します)
Randombook
このブログで紹介したことのある本をランダム表示。
Randomusic
このブログで紹介したことのある音をランダム表示。
自分がらみのリンク
はやしのブログ書籍一覧
このブログで言及された書籍の一覧。
はやしのブログ音盤一覧
このブログで言及された音盤の一覧。
最近のおすすめ本
最近のおすすめ音

Copyright © [ はやしのブログ ]
No right reserved except those which belong to someone else.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]