-
有限狀態文法
鎖定
有限狀態文法(finite state grammar)形式文法的一種類型.
- 中文名
- 有限狀態文法
- 外文名
- finite state grammar
在文法G= (VN,V丁，S,屍)中，如果重寫規則的形式為A-＞aQ或A-＞a，其中A和Q是非終極符號，a是終極符號，那麼就把這種文法稱為有限狀態文法，又稱3型文法.如果在重寫規則A-＞aQ中，把A和Q看成不同的狀態，那麼當從狀態A到狀態Q時，就可生成一個終極符號a，這樣便可把有限狀態文法想象為一種生成裝置，這種裝置每次只能生成一個終極符號，而每一個非終極符號都與一個特定的狀態相聯繫，由此可以建立有限狀態文法與有窮狀態自動機的關係.
