A New Approach to Formal Language Theory using Kolmogorov Complexity

Title: A New Approach to Formal Language Theory using Kolmogorov Complexity

Abstract: This research article proposes a new approach to formal language theory using Kolmogorov complexity, a concept from algorithmic information theory. The main results include an alternative to pumping lemmas, a new characterization for regular languages, and a new method to separate deterministic context-free languages and non-deterministic context-free languages. The use of 'compressibility arguments' is illustrated by many examples, and the approach is successful at the high end of the Chomsky hierarchy, allowing non-recursiveness to be quantified in terms of Kolmogorov complexity.

Main Research Question: Can Kolmogorov complexity, a concept from algorithmic information theory, be used to develop a new approach to formal language theory?

Methodology: The researchers used Kolmogorov complexity, a measure of the computational complexity of a string, to develop a new approach to formal language theory. They presented theorems on how to use Kolmogorov complexity as a concrete and powerful tool, and applied these theorems to various aspects of formal language theory.

Results: The researchers presented an alternative to pumping lemmas, a new characterization for regular languages, and a new method to separate deterministic context-free languages and non-deterministic context-free languages. They also demonstrated that the approach is successful at the high end of the Chomsky hierarchy, allowing non-recursiveness to be quantified in terms of Kolmogorov complexity.

Implications: The new approach to formal language theory using Kolmogorov complexity could have significant implications for the field. It may lead to new insights and understanding, and could potentially be applied to other areas of computer science and mathematics. Additionally, the results could have practical applications in areas such as natural language processing and machine learning.

Link to Article: https://arxiv.org/abs/0110040v1 Authors: arXiv ID: 0110040v1