Automata-theory-introduction-to-grammars

文法入門

用語の文学的意味では、文法は自然言語での会話の構文規則を示します。 言語学は、英語、サンスクリット語、北京語などの自然言語の始まり以来、文法を定義しようとしました。

形式言語の理論は、コンピューターサイエンスの分野で広く適用されます。 Noam Chomsky は、1956年にコンピューター言語の記述に効果的な文法の数学モデルを提供しました。

文法

文法 G は、正式には4タプル（N、T、S、P）として記述できます。

• N または* V〜_ [。small]＃N＃_〜*は、変数または非終端記号のセットです。
• T または ∑ は、ターミナル記号のセットです。
• S は開始記号と呼ばれる特別な変数で、S∈N
• P は、ターミナルおよび非ターミナルの生産ルールです。 プロダクションルールの形式はα→βです。αとβはV〜_ [。small]＃N＃_〜on stringsの文字列であり、αの少なくとも1つのシンボルはV〜N〜に属します。

例

文法G1-

（\ {S、A、B}、\ {a、b}、S、\ {S→AB、A→a、B→b}）

ここに、

• * S、A、、および *B は非終端記号です。
• a および b は端末記号です
• S は開始記号、S∈N
• プロダクション、 P：S→AB、A→a、B→b

例

文法G2-

（（\ {S、A}、\ {a、b}、S、\ {S→aAb、aA→aaAb、A→ε}）

ここに、

• S および A は非終端記号です。
• a および b はターミナルシンボルです。
• *ε*は空の文字列です。
• S は開始記号、S∈N
• 生産* P：S→aAb、aA→aaAb、A→ε*

文法からの派生

文字列は、文法のプロダクションを使用して他の文字列から派生する場合があります。 文法 G に*α→β*の生成がある場合、 xαy は G の xβy を導出すると言うことができます。 この派生は次のように書かれています-

*_xαy [.sy-r]＃⇒[.oxbr] ## G ### xβy_*

例

文法を考えてみましょう-

G2 =（\ {S、A}、\ {a、b}、S、\ {S→aAb、aA→aaAb、A→ε}）

派生できる文字列のいくつかは-

S⇒[.underline] aA b本番を使用S→aAb

⇒a [.underline] aA bb（プロダクションaAを使用）→aAb

⇒aaa [.underline] A bbb（プロダクションaAを使用）→aAb

⇒プロダクションAを使用したaaabbb→ε