context-free-grammar - 言語が正規ではない半正規文法の例

Question

「半正規」文法は、次の形式の規則のみを許可する文法です。

X → y
X → y Y
X → Y y

ここで、XとYは任意の単一の非終端記号であり、xとyは任意の単一の終端記号です。

たとえば、これは言語a +b+の半正規文法です。

S → a S
S → a A
A → A b
A → b

言語が正規言語ではない半正規文法の例を挙げてください。言語が何であるか、そしてなぜそれが規則的でないのかを必ず言ってください。

Answer 1

どうですか

S := aT | -
T := Sb

-は空の文字列を表すことに注意してください。必要に応じて、規則性を変更せずに、これを単一の終端記号に置き換えることができます。これによりa^n b^n、正規の非正規言語である language が生成されます。正規言語のポンピング補題または Myhill-Nerode の定理を使用して、同じくらい簡単に証明できます。