Viewing First-order Language from Chomsky's Hierarchy
Heng Gu
Abstract
Heng Gu
Abstract
First-order languages are usually referred as formal languages in usual logic textbooks, but generative rules generally defines formula,rather than shows how to construct formula.In this article we illustrate a new understanding of the process of the formation of first-order languages from the point of view of Chomsky formal grammars.As a first-order language is recursive,so it must be a recursively enumerable language, thus there is a formal grammar to generate it.We illustrates one which is also a context-free grammar, hence any first-order language is more than a recursively enumerable language but also a context-free language. Furthermore,it is proved that first-order languages can also be generated with regular grammars by making use of the Godel encoding.Thus we can make a stronger conclusion that any first-order language is also a regular language.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
First-order languages are usually referred as formal languages in usual logic textbooks, but generative rules generally defines formula,rather than shows how to construct formula.In this article we illustrate a new understanding of the process of the formation of first-order languages from the point of view of Chomsky formal grammars.As a first-order language is recursive,so it must be a recursively enumerable language, thus there is a formal grammar to generate it.We illustrates one which is also a context-free grammar, hence any first-order language is more than a recursively enumerable language but also a context-free language. Furthermore,it is proved that first-order languages can also be generated with regular grammars by making use of the Godel encoding.Thus we can make a stronger conclusion that any first-order language is also a regular language.
Key concepts: Chomsky hierarchy, Computer science, Recursively enumerable language, Formal grammar, Generative grammar, Formal language, Context-sensitive grammar, Regular grammar