形式文法
以下の例では、形式言語を集合の内包的記法で記述している。
N = { S , B } {\displaystyle N=\left\{S,B\right\}} , Σ = { a , b , c } {\displaystyle \Sigma =\left\{a,b,c\right\}} の文法 G {\displaystyle G} について、生成規則 P {\displaystyle P} が以下の規則から構成される。
1. S ⟶ a B S c {\displaystyle S\longrightarrow aBSc}
2. S ⟶ a b c {\displaystyle S\longrightarrow abc}
3. B a ⟶ a B {\displaystyle Ba\longrightarrow aB}
4. B b ⟶ b b {\displaystyle Bb\longrightarrow bb}
また、非終端記号 S {\displaystyle S} は開始記号である。 L ( G ) {\displaystyle {\boldsymbol {L}}(G)} における文字列生成の実例は以下のようになる。
S ⟶ ( 2 ) a b c {\displaystyle {\boldsymbol {S}}\longrightarrow (2)abc}