scientific article; zbMATH DE number 3850487
[For the entire collection see Zbl 0527.00035.] The paper studies normal systems (the derivation steps are of the form u\(v\Rightarrow wu\), (v,w) a production). The generative power of such systems under certain limiting assumptions is discussed. Th role of terminal subalphabets in normal systems with productions of the (A,w), A a (nonterminal) symbol, is investigated. If we introduce further conditions and transformations (e.g. codings, homomorphisms, nonerasing/erasing productions) we obtain more than 30 classes of languages. Inclusion theorems for the classes are derived. Relations to other rewriting systems are also discussed (e.g. L-systems).
- Comparison of basic language generating devices (non-deterministic systems)
- Simple restriction in context-free rewriting
- Analytic approach to context-free languages in the Greibach normal form
- A characterisation of deterministic context-free languages by means of right-congruences
- scientific article; zbMATH DE number 4009838
- Comparison of basic language generating devices (non-deterministic systems)
- scientific article; zbMATH DE number 4009838 (Why is no real title available?)
- scientific article; zbMATH DE number 4043269 (Why is no real title available?)
- scientific article; zbMATH DE number 4100625 (Why is no real title available?)
- Canonical systems which produce periodic sets
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3319784)