context-free-grammar - 文脈自由文法

Question

この概念を理解するのに助けが必要です。

本は述べています

G1:
    A→0A1
    A→B
    B→#

G1文字列を生成すると述べています000#111

プロセスを示しています

A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111

ここで何が起こっているのか理解しています。私が確信していないのは、それが無限にループできるかどうかです。

例えば：

このプロセスを使用してG1生成することもできます0#1

A → 0A1 → 0B1 → 0#1

この本はこの部分を明確に説明していません。ありがとう

Answer 1

はい、任意のプロダクションを無限に適用できるため、（この場合もほとんどの場合も）無限の数の文字列が生成されます。この文法は、フォーム 0 ⁿ #1 ^{nのすべての文字列を生成します}

Answer 2

はい、確かに。与えられた文法は0#1言語も生成します。ことは十分に明らかです。ご覧のとおり、生成された言語 0#1 は、同じ文法によって生成された以前の言語のサブセットです。