While doing some reading on rings, I came across some interesting stuff about
\nMonoids and syntax. That’s right up my alley, so I decided to write a post about that.<\/p>\n
<\/p>\n
We start by defining a new property for monoids – a kind of equivalence If we have a monoid congruence relation “~”, then we can obviously use it to create a collection of equivalence classes, called congruence classes<\/em>. If a is a member of monoid (M,º), then we can define the congruence class [a]={m∈M | x~a } – that is, the set of objects in M that are “~” with a. <\/p>\n We can then define a new operation on the congruence classes: if a and b are members of a monoid (M,º), then we can define an operation “*” by Now, we take a new step, and this is where it starts to get really interesting. Remember how I described the relationship between monoids and computing devices? We’re going to start taking advantage of that. If we take a monoid, and use concatenation In automata theory, we talk about formal languages, which are specific sets of strings of symbols. A formal language is usually described by some system of rules, which describe This language consists of sequences of open and close parens where the number of opens and closes is balanced: strings like “()”, “(())”, “((()(()(()))))”, and so on.<\/p>\n If we think of a monoid as a meta-computing machine, then we can We can start by defining a syntactic quotient<\/em>, using contatenation to denote the monoid operator. If M is a monoid, and S is a subset of M, We can then use the syntactic quotients to define congruence relations, a ~s<\/sub> b ⇔ (∀x,y∈M: xay∈S ⇔ xby∈S<\/p>\n So, here’s where the connection to computable languages comes in. The syntactic quotient, following the procedure above, defines a new monoid – the syntactic monoid of S, which we call M(S). The syntactic monoid of S is a monoid which accepts<\/em> In particular, we can define what it means for a language to be recognizable by a There’s more to it than this – transition monoids are particularly interesting. But that’s enough for this post. We’ll save it for later.<\/p>\n","protected":false},"excerpt":{"rendered":" While doing some reading on rings, I came across some interesting stuff about Monoids and syntax. That’s right up my alley, so I decided to write a post about that.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[69,79],"tags":[],"class_list":["post-608","post","type-post","status-publish","format-standard","hentry","category-abstract-algebra","category-computation"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-9O","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/608","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=608"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/608\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=608"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=608"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=608"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nrelation called a monoid congruence<\/em>. A Monoid congruence defines
\nequivalence classes within the set of values in a monoid. The monoid congruence
\nrelation is generally written as “~”, and it’s a relation between two values in a
\nmonoid: ~⊆M×M. A monoid congruence has all of the usual properties
\nof an equivalence relation: it’s symmetric, reflexive, and transitive. It also
\nrespects the monoid operator: if a, b, c, and d are all members of a monoid M,
\na~c, and b~d, then aºb~cºd. <\/p>\n
\n[a]*[b]=[aºb]. If you look at the set of congruence classes of M given by “~”, and the “*”, what do you get? Another monoid<\/em>, which we call a quotient monoid<\/em>. The quotient monoid created by a particular congruence relation “~” is
\nwritten M\/~.<\/p>\n
\nas the notation for the monoid operator, then we can describe products as strings: “abc” is (aºb)ºc. <\/p>\n
\nhow the strings in the language are generated. For a very simple example, we can
\nuse a regular expression, like “a+<\/sup>b*<\/sup>” to represent the language consisting of any number of “a”s, possibly followed by any number of “b”s. We can
\ntalk about more complicated languages, by using grammars. For example, the classic
\nfirst language that can’t be described by simple regular expressions is the following:<\/p>\n\nX<\/em> → (X<\/em>)\nX<\/em> → X<\/em> X<\/em>\nX<\/em> → ε\n<\/pre>\n
\ntalk about the kinds of languages that can be accepted by a particular
\nmonoid – that is, if we’re working with a machine built from the monoid, what kinds of languages can that machine accept? It turns out that we can define that
\nset using monoid quotients!<\/p>\n
\nthen we can define left and right syntactic quotients<\/em> of S:<\/p>\n\n
\nwritten S\/m = { a∈M | am ∈ S }.<\/li>\n
\nwritten nS = { b∈M | mb∈S }.<\/li>\n<\/ul>\n
\nexactly as we did above. We get two congruence relations, the right syntactic equivalence<\/em>, ~s, which is the congruence relation induced by the right syntactic quotient, and the left syntactic equivalence<\/em> s~, which is the congruence relation implied by the left syntactic quotient. And finally, we can define a total syntactic congruence (also called a double-sided congruence), written ~s<\/sub> using both:<\/p>\n
\nthe set S. We call a language<\/em> – consisting of the strings of symbols that
\nconcatenated together by M’s monoid operator result in values in S. So we’ve finally really gotten to the point where we can really see how a monoid represents a computing device. In computation theory, we can describe every computing device in terms of languages. We can likewise describe computable languages in terms of monoids.<\/p>\n
\nmonoid, M. Take a language, L⊆M. If the set of quotients {L\/m|m∈M} is finite,
\nthen L is recognizable by M. <\/p>\n