Syntactic monoid

In mathematics and computer science, the syntactic monoid of a formal language is the smallest monoid that recognizes the language . The free monoid on a given set is the monoid whose elements are all the strings of zero or more elements from that set, with string concatenation as the monoid operation and the empty string as the identity element. Given a subset of a free monoid , one may define sets that consist of formal left or right inverses of elements in . These are called quotients, and one may define right or left quotients, depending on which side one is concatenating. Thus, the right quotient of by an element from is the set Similarly, the left quotient is The syntactic quotient induces an equivalence relation on , called the syntactic relation, or syntactic equivalence (induced by ). The right syntactic equivalence is the equivalence relation Similarly, the left syntactic equivalence is Observe that the right syntactic equivalence is a left congruence with respect to string concatenation and vice versa; i.e., for all . The syntactic congruence or Myhill congruence is defined as The definition extends to a congruence defined by a subset of a general monoid . A disjunctive set is a subset such that the syntactic congruence defined by is the equality relation. Let us call the equivalence class of for the syntactic congruence. The syntactic congruence is compatible with concatenation in the monoid, in that one has for all . Thus, the syntactic quotient is a monoid morphism, and induces a quotient monoid This monoid is called the syntactic monoid of . It can be shown that it is the smallest monoid that recognizes ; that is, recognizes , and for every monoid recognizing , is a quotient of a submonoid of . The syntactic monoid of is also the transition monoid of the minimal automaton of . A group language is one for which the syntactic monoid is a group. The Myhill–Nerode theorem states: a language is regular if and only if the family of quotients is finite, or equivalently, the left syntactic equivalence has finite index (meaning it partitions into finitely many equivalence classes).

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (7)

Related concepts (11)

Related courses (1)

Related lectures (14)

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

Transformation semigroup

In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations (functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transformation (or composition) monoid. This is the semigroup analogue of a permutation group. A transformation semigroup of a set has a tautological semigroup action on that set. Such actions are characterized by being faithful, i.e., if two elements of the semigroup have the same action, then they are equal.

Semiautomaton

In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q.

String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. A string is a finite sequence of characters. The empty string is denoted by . The concatenation of two string and is denoted by , or shorter by . Concatenating with the empty string makes no difference: .

We determine the dimension of every simple module for the algebra of the monoid of all relations on a finite set (i.e. Boolean matrices). This is in fact the same question as the determination of the dimension of every evaluation of a simple correspondence ...

2020

Let epsilon be a set of points in F-q(d). Bennett et al. (2016) proved that if \epsilon\ >> [GRAHICS] then epsilon determines a positive proportion of all k-simplices. In this paper, we give an improvement of this result in the case when epsilon is the Car ...

Elsevier Science Bv2017

Polarization and Channel Ordering: Characterizations and Topological Structures

Rajai Nasser

Information theory is the field in which we study the fundamental limitations of communication. Shannon proved in 1948 that there exists a maximum rate, called capacity, at which we can reliably communicate information through a given channel. However, Sha ...

EPFL2017

Formal Languages: Concepts CS-320: Computer language processing

Covers the fundamental concepts of formal languages, including alphabets, words, languages, and word equality.

Formal Languages: Concepts CS-320: Computer language processing

Covers the basics of formal languages, including alphabets, words, and languages, as well as operations like concatenation and reversal.

Abstract algebra and type classes CS-210: Functional programming

Covers abstract algebra concepts using type classes in Scala, including defining monoids, generalizing reduce functions, and typeclass laws.