文法によって生成された言語
文法から派生できるすべての文字列のセットは、その文法から生成された言語であると言われます。文法によって生成された言語G によって正式に定義されたサブセットです
L（G）= {W | W∈Σ*、S ⇒ 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に変換します。
例
Problem− L（G）= {a m b n | m≥0かつn> 0}。私たちは文法を見つけなければなりませんG を生成します L(G)。
Solution
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}）
例
Problem− L（G）= {a m b n | m> 0およびn≥0}。L（G）を生成する文法Gを見つける必要があります。
Solution −
L（G）= {a m b n | m> 0かつn≥0}の場合、受け入れられる文字列のセットは次のように書き換えることができます。
L（G）= {a、aa、ab、aaa、aab、abb、……。}
ここで、開始記号は、少なくとも1つの「a」の後にnullを含む任意の数の「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}）