Regular Grammars and Regular Expressions

Contents

• Tree Grammar
• Definitions
• Regular tree grammar and recognizable tree languages
• Regular expressions. Kleene's theorem for tree languages.
• Substitution and iteration
• Regular expressions and regular tree languages.
• Regular equations.
• Context-free word languages and regular tree languages
• Beyond regular tree languages: context-free tree languages
• Context-free tree languages
• IO and OI tree grammars
• Exercises
• Bibliographic notes