On derivation preservation (Q1058859)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On derivation preservation |
scientific article |
Statements
On derivation preservation (English)
0 references
1984
0 references
A homomorphism h between the production sets of two context-free grammars \(G_ 1\) and \(G_ 2\) is said to ''preserve derivations'' if it maps derivations to derivations and terminal derivations to terminal derivations. The concept of derivation preservation is common to some of the grammatical relations introduced in the literature (cover, undercover, Reynolds cover and SI-cover). The paper studies the properties of a nonterminal relation induced a by derivation preserving homomorphism h. Finally, it is shown that it is decidable whether or not homomorphism h preserves derivations in a system \((G_ 1,G_ 2,h)\).
0 references
grammatical covering
0 references
context-free grammars
0 references
derivation preservation
0 references
0 references