正則文法
外觀
在電腦科學中,正則文法是產生式規則取下述形式的一種形式文法(N, Σ, P, S):
下面給出一個正則文法的例子: 文法G = (N, Σ, P, S),其中N = {S, A},Σ = {a, b, c},S是起始符號,P包含下述規則:
這個文法描述的語言也可以用正規表示式a*bc* 來表達。
正則文法描述的語言構成了正規語言類,正規語言類中的語言也可以由有限狀態自動機或正規表示式來表達。
| |||||||||||||||||||||||||||||||||||||||||||||||||
每個語言範疇都是其直接上面的範疇的真子集 每個語言範疇內的語言都可以用同一行的文法和自動機表示 |