1.7 KiB
created, course, topic, related, type, status, tags
| created | course | topic | related | type | status | tags | |
|---|---|---|---|---|---|---|---|
| 2026-04-28 14:25 | lecture | 🔴 |
|
📌 Summary
[!abstract]
📝 Content
A containment hierarchy of classes of formal grammars. Grammars are classified into four types with different limitations.
Type 0
no restrictions
Type 1
Each rule sans(w)_1 -> sans(w_2) satisfies sans(abs(w_1) <= abs(w_2)) with the exception that sans(S) -> epsilon is allowed if sans(S) does not occur on any right hand side of rules.
sans(abs(w_1) <= abs(w_2)) implies that no shortening rules are allowed.
Type 2 (context free)
Same restriction as #Type 1 and additionally for each rule sans(w_1 -> w_2) the string sans(w_1) contains only a single variable (i.e. sans(w_1 in V))
Type 3 (regular)
Same restriction as #Type 2 and additionally sans(w_2 in Sigma union Sigma V)), i.e. the right hand side is either a single terminal symbol or a terminal symbol followed by a variable.
[!REMARK] The order of the variable and the terminal symbol is chosen arbitrarily. Important is just that within a regular grammar only a single order occurs. If for all rules
sans(w_2 in Sigma union V Sigma)it would also be a regular grammar.
Definition
A language sans(L subset Sigma^*) is said to be of type 0 (1,2,3) if there exist a type 0 (1,2,3) grammar sans(G) for which sans(L(G) = L).
[!REMARK] In order to show that a language is op type 0 (1,2,3) one thus just has to find a corresponding grammar. In order to show that a grammar is not of type 0 (1,2,3) one has to prove that no type 0 (1,2,3) grammar can exist generating the corresponding language.