One application of real-valued interpretation of formal power series

✍ Scribed by An.A. Muchnik

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 168 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00369-9

✦ Synopsis

We deÿne two natural properties of context-free grammars. The ÿrst property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the ÿrst type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are e ectively separable.