タイプ3の文法 - 正規表現

Question

私はタイプ3グラマは、これらの作品A、Bは非端子とAの端末

iがされている

A-> aB 
A-> Ba 

の両方を持つことができないことに注意を読みましたタイプ3について十分に知っていますが、私は上記を理解できません。

Answer 1

これらの両方の制作を可能にすると、タイプ3の意味が変わります。次のような文法を書くことができます：

A -> '(' B 
B -> A ')' 
A -> '1' 

あなたが開始非末端であることを前提とした場合は、お使いの言語があなたのすべての単語

((...((1))...)) 

両側に括弧の数を与えます同じです。しかし、これはタイプ3の言語ではありません（非形式的には、正しいパーサーがカウントする必要があるため、有限状態にはなりません）。