2013Journal of Bijie UniversityRequires access

Viewing First-order Language from Chomsky's Hierarchy

Heng Gu

Open publisher page 0 citations

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.

About this research paper

What this paper is about

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.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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.

Key concepts: Chomsky hierarchy, Computer science, Recursively enumerable language, Formal grammar, Generative grammar, Formal language, Context-sensitive grammar, Regular grammar

Related papers

Back to paper searchBrowse research topicsOriginal source
Viewing First-order Language from Chomsky's Hierarchy — Research Paper | ScholarLens