Formal Languages, Automata and Numeration Systems 2

Applications to Recognizability and Decidability

Michel Rigo

• Publisher: Wiley-ISTE
• Year: 2014
• ISBN:
  9781119042860
• Edition: 1
• Topic: Technology & Engineering
• Subtopic: Signals & Signal Processing
• Index: Technology & Engineering

The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi) or between combinatorics on words and number theory has paved the way to recent dramatic developments, for example, the transcendence results for the real numbers having a "simple" binary expansion, by B. Adamczewski and Y. Bugeaud.

This book is at the heart of this interplay through a unified exposition. Objects are considered with a perspective that comes both from theoretical computer science and mathematics. Theoretical computer science offers here topics such as decision problems and recognizability issues, whereas mathematics offers concepts such as discrete dynamical systems.

The main goal is to give a quick access, for students and researchers in mathematics or computer science, to actual research topics at the intersection between automata and formal language theory, number theory and combinatorics on words.

The second of two volumes on this subject, this book covers regular languages, numeration systems, formal methods applied to decidability issues about infinite words and sets of numbers.

1

Crash Course on Regular Languages

The theory of finite automata has preserved from its origins a great diversity of aspects. From one point of view, it is a branch of mathematics connected with the algebraic theory of semigroups and associative algebras. From another point of view, it is a branch of algorithm design concerned with string manipulation and sequence processing. It is perhaps this diversity that has enriched the field to make it presently one with both interesting applications and significant mathematical problems.

Dominique Perrin [PER 90]

This chapter is intended to be short. Automata theory and formal language theory have been developed for more than 50 years. There are many textbooks devoted to these theories (and we can easily find series of exercises). To cite just a few (all these books cover in particular what is nowadays considered as classical material): [HOP 79] or [SUD 06] where the focus is oriented toward the computational models and the corresponding algorithms, the comprehensive [SAK 09] where a wider perspective, a more general algebraic framework and emphasis on the underlying structures are provided. I personally like the presentation and the material covered in [SHA 08]. I can also mention [LAW 04] (for a light introduction to the syntactic monoid of a language) or the classic [EIL 74]. See also, the survey [YU 97] or [PER 90] for a condensed exposition.

We have already encountered the notion of automaton in several sections of this book: the formal presentation of deterministic automaton first appeared in definition 2.23. Then the extended model with output was given in definition 2.27, Volume 1, to deal with automatic sequences. We will work only with these types of finite machines¹.

First, we will provide summary of some basic results about finite automata and regular languages. Then, we will select some particular topics related to the main themes of the book: recognizable sets of numbers and morphic or automatic words. The lastsection will present regular languages of polynomial growth. Thus, their characterization is applied to growing letters in a morphic word. Also, this chapter will serve as a preparation for the last chapter of the book where automata will play an important role when dealing with decision procedures. For an easy understanding of Chapter 3, the readers familiar with automata theory should consult sections 1.3 and 1.7.

1.1. Automata and regular languages

We begin with a definition that we have already described in definition 2.23, Volume 1. But, here the focus is put on the words, and thus on the language that is accepted by such a machine.

DEFINITION 1.1.– A deterministic finite automaton, or DFA for short, over an alphabet B is given by a 5-tuple

= (Q, q₀,B, δ, F), where Q is a finite set of states, q₀ ∈ Q is the initial state, δ : Q × B → Q is the transition function and F ⊆ Q is the set of final states. The map δ can be extended to Q × B* by setting δ(q, ε) =...

Table of contents

• Cover
• Contents
• Dedication
• Title Page
• Copyright
• Foreword
• Introduction
• 1 Crash Course on Regular Languages
• 2 A Range of Numeration Systems
• 3 Logical Framework and Decidability Issues
• 4 List of Sequences
• Bibliography
• Index
• Summary of Volume 1