Automata-theory-language-generated-by-grammars

文法によって生成された言語

文法から派生できるすべての文字列のセットは、その文法から生成された言語と呼ばれます。 文法 G によって生成された言語は、

L（G）= \ {W | W∈∑ 、S [.sy-r]＃⇒[.oxbr] G# *W }

• L（G1）= L（G2）の場合、文法 *G1 は文法 G2 と同等です。

例

文法がある場合

G：N = \ {S、A、B} T = \ {a、b} P = \ {S→AB、A→a、B→b}

ここで、 S は AB を生成し、 A を a に、 B を b に置き換えることができます。 ここで、受け入れられる文字列は ab のみです。つまり、

L（G）= \ {ab}

例

次の文法があると仮定します-

G：N = \ {S、A、B} T = \ {a、b} P = \ {S→AB、A→aA | a、B→bB | b}

この文法によって生成された言語-

L（G）= \ {ab、a ^ 2 ^ b、ab ^ 2 ^、a ^ 2 ^ b ^ 2 ^、………}

\ {a ^ m ^ b ^ n ^ | m≥1およびn≥1}

言語を生成する文法の構築

一部の言語を検討し、それらの言語を生成する文法Gに変換します。

例

*_問題_* -仮定、L（G）= \ {a ^ m ^ b ^ n ^ | m≥0およびn> 0}。 * L（G）*を生成する文法 *G* を見つける必要があります。

溶液

L（G）= \ {a ^ m ^ b ^ n ^ | m≥0およびn> 0}

受け入れられた文字列のセットは次のように書き換えることができます-

L（G）= \ {b、ab、bb、aab、abb、……。}

ここで、開始記号には、nullを含む任意の数の「a」が先行する少なくとも1つの「b」が必要です。

文字列セット\ {b、ab、bb、aab、abb、……。}を受け入れるために、プロダクションを取りました-

S→aS、S→B、B→bおよびB→bB

S→B→b（承認済み）

S→B→bB→bb（承認済み）

S→aS→aB→ab（承認済み）

S→aS→aaS→aaB→aab（承認済み）

S→aS→aB→abB→abb（承認済み）

したがって、L（G）のすべての文字列が、プロダクションセットによって生成された言語で受け入れられることを証明できます。

したがって、文法-

G：（\ {S、A、B}、\ {a、b}、S、\ {S→aS | B、B→b | bB}）

例

*_問題_* -仮定、L（G）= \ {a ^ m ^ b ^ n ^ | m> 0およびn≥0}。 L（G）を生成する文法Gを見つける必要があります。

*_ソリューション_* -

L（G）= \ {a ^ m ^ b ^ n ^ | m> 0およびn≥0}、受け入れられる文字列のセットは次のように書き換えることができます-

L（G）= \ {a、aa、ab、aaa、aab、abb、……。}

ここで、開始記号には、少なくとも1つの「a」とそれに続くヌルを含む任意の数の「b」が必要です。

文字列セット\ {a、aa、ab、aaa、aab、abb、……。}を受け入れるために、プロダクションを取りました-

S→aA、A→aA、A→B、B→bB、B→λ

S→aA→aB→aλ→a（承認済み）

S→aA→aaA→aaB→aaλ→aa（承認済み）

S→aA→aB→abB→abλ→ab（承認済み）

S→aA→aaA→aaaA→aaaB→aaaλ→aaa（受け入れられます）

S→aA→aaA→aaB→aabB→aabλ→aab（承認済み）

S→aA→aB→abB→abbB→abbλ→abb（承認済み）

したがって、L（G）のすべての文字列が、プロダクションセットによって生成された言語で受け入れられることを証明できます。

したがって、文法-

G：（\ {S、A、B}、\ {a、b}、S、\ {S→aA、A→aA | B、B→λ| bB}）