On regular languages

-

In this series of posts, I wish to introduce a notion of automatic groups, i.e. groups which has an automatic presentation. To do so, we need to revise notions of regularity and that of automatic relation. Let us start with a notion of regularity.

Regular Languages
The concept of regularity for formal languages can be approached from several sides. We are going to define regulaity using finite state machines. We start with a finite set $\Sigma$ called an \emph{alphabet}. By concatenating elements of this alphabet, we can form \emph{words} or \emph{strings}. For example, if $\Sigma = \{0,1\}$, then possible words are $01$ and $00111$. Let us denote a collection of all possible words in the given alphabet $\Sigma$ as $\Sigma^*$. We refer to subsets of $\Sigma^*$ as \emph{formal languages} or \emph{languages} for short. There are might be different kinds of languages, in fact $\vert 2^{\mathbb{N}}\vert \}$ many, some of them easy to describe, while others extremely complicated. We are interested in languages which provide easy way to check membership, i.e. given a word $w$, we ask if $w\in L$ for some language $L$. One of such classes of languages are called \emph{regular languages}. To define such a language, we need to use machine called finite automata, which are going to be defined below. 
(Deterministic) Finite automata 
Let $M = (Q, \Sigma, \delta, s_0, F)$ be 5-tuple, where $Q$ is a finite set, $\Sigma$ is the alphabet, $\delta:Q\times \Sigma\to Q$ is a transition function, $s_0\in Q$ and $F\subseteq Q$ a set of accepting states. Given a word $w = w_0w_1\ldots w_{n-1}$ it induces a sequence of states $q = q_0q_1\ldots q_{n-1}$ as follows:
  1. $q_0 = s_0$
  2. $\delta(q_i,w_i) = w_{i+1}$, for all $i$.   
We say that a word $w$ is accepted by the deterministic finite automaton $M$, if $q_{n-1}\in F$, i.e. it ends up in an accepting state. Let $L(M) = \{w\mid M \text{ accepts }w\}$ denote a language \emph{recognized} by $M$. Now we are ready to define a notion of a regular language.

Regularity
A language $L$ is called regular if there is a deterministic finite automaton recognizing it

There is also a notion of a nondeterministic finite automaton. We give its definition below.
Nondeterministic finite automata 
Let $M = (Q, \Sigma, \delta, s_0, F)$ be a 5-tuple as before with only exception that $\delta:Q\times S \to \mathcal{P}(Q)$. In other words, there might be several outgoing edges corresponding for some pair of state and letter. Observe that given word $w$, now induces several runs, in fact up to $Q^{\vert w \vert}$. A nondeterministic finite automaton $M$ accepts a word $w$ if there is a accepting run, i.e. it ends at an accepting state. Comparing two kinds of automata, it is clear that nondeterministic finite automata subsume deterministic ones. However, they turn out to be equivalent. This equivalence is captured in the following proposition, proof of which can be found in virtually every book on automata theory.

Equivalence of deterministic and nondeterministic finite automata
A language is recognized by a nondeterministic finite automata if and only if it is regular.

Let us end this post here. I hope to go through automatic relations in the next post. 

Comments

Post a Comment

Popular posts from this blog

On learning C++

-
"You are number of languages that you know" said one of the quotes attributed to Al-Farabi, which my school teacher used to tell us. Indeed almost all languages describe the same objects: humans, animals, nature and universe in general. However, the way each language does so might differ from another one. This difference makes learning new languages fun. A somewhat similar statement can be said about programming languages. Almost all of them perform some kind of logical and computational transformations on given data, however the ways they do so might significantly differ. Having learnt some Python to play with Machine Learning (ML) algorithms, I wanted to explore other programming languages. The first language which came to mind was C++. It is one of the languages used to code massive and complex software systems. So did I explored using a website  https://www.programiz.com/cpp-programming . How it went The installation part went easy. The application XCode does a solid ...
Read more

Neural Networks as Morphisms

-
Image
Abstract This set of notes attempts to study possibility of constructing categories with neural nets as morphism and functors. The reason for such construction comes stems from possible enriching connections between category theory and deep learning. Usually Category Theory is used to formalize abstractions of the given concrete objects. On the other hand, Deep Learning is mostly used in constructing explicit neural network based mappings between various spaces given by sampled datasets. The notes explores if it is possible to leverage on strengths of category theory and deep learning in order to represent more abstract concepts and processes. Introduction Motivation: The main motivation for development of framework if two folds. Firstly, it might shed a new light for representing more abstract objects, such as movements and processes. Secondly, we leverage on rich experience of building deep neural nets accumulated in Machine Learning community. Abs...
Read more

On ideas behind Bayesian Learning

-
When one reads about Machine Learning (ML) or Artificial Intelligence (AI) it is common to come across a list of approaches to AI such as: symbolic reasoning, Bayesian learning, artificial neural networks and so on. Seeing this list I was puzzled with a notion of Bayesian Learning. The only thing I knew with a name Bayes in its name was a famous Bayes's theorem which states that \[ P(H\mid E) = \frac{P(E\mid H)P(H)}{P(E)} \] where $P(H)$ and $P(H\mid E)$ denote prior and posterior probabilities of hypothesis $H$, respectively. What puzzled me is the application of such a simple looking formula to draw patterns from data. In order to learn basic principles of Bayesian learning, I decided to consult Wikipedia and few online tutorials. This post is about results of this exploration. Wikipedia says Bayesian learning (inference?) is a method of statistical inference in which Bayes's theorem is used to update the probability for a hypothesis as more evidence or informatio...
Read more