How to prove that a language is regular or star-free?

The class of regular languages is the smallest class of languages containing the finite languages that is closed under finite union, finite product and star. The definition of star-free languages follows the same pattern, with the difference that the star operation is replaced by the complement. In other words, the class of star-free languages is the smallest class of languages containing the finite languages that is closed under finite union, finite product and complement.

In this lecture, I will present some standard and less standard methods to prove that a language is regular or star-free.

Date and Venue

Start Date
Venue
Online Zoom meeting
End Date

Speaker

Jean-Eric Pin

Speaker's Institution

IRIF, CNRS

Files

Area

Semigroups, Automata and Languages

Financiamento