Abstract Regularity and non-locality of string languages and tree languages are considered. DTDs correspond to such tree-local languages. When we talk about regularity, we usually consider sets of strings. The above three conditions are equivalent.
Derivation is defined in an usual manner.
A string s is generated from the string-regular grammar G if s is derived from the start symbol S. 2. We now introduce a new concept called locality. The first occurrence of 'a' has to be followed by 'b', while the second occurrence has to be followed by 'c'. Now, let us simplify the definition of string-local grammars. Here is a revised definition of string-local grammars.