Automata Step by Step

Now we also need definition of “regular grammar”

Regular Grammars:

Regular grammars describe exactly all regular languages and are in that sense equivalent to finite state automata and regular expressions. Moreover, the right regular grammars by themselves are also equivalent to the regular languages, as are the left regular grammars.

Every regular grammar is a context-free grammar. Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions.

What is a regular language? It is important to understand “regular language” for better understanding of above definitions. We will discuss it in our next post..

Automata Step by Step

Today, we will discuss “Regular expressions”.

Regular expressions:

A regular expression (also "RegEx" or "regex”) is a string that is used to describe or match a set of strings, according to certain syntax rules. The specific syntax rules vary depending on the specific implementation, programming language, or library in use. Additionally, the functionality of regex implementations can vary between versions

In another words, a regular expression, often called a pattern, is an expression that describes a set of strings. They are usually used to give a concise description of a set, without having to list all elements. For example, the set containing the three strings Handel, Händel, and Haendel can be described by the pattern "H(ä|ae?)ndel" (or alternatively, it is said that the pattern matches each of the three strings). In most formalism, if there is any regex that matches a particular set then there are an infinite number of such expressions.

Automata Step by Step

Now we will define “Sequence”

Sequence:
A sequence is an ordered list of objects (or events). Like a set, it contains members (also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and the exact same elements can appear multiple times at different positions in the sequence.

Now we will define “Language”.

Language(or Formal Language):

A Language is a set of strings over a given input alphabet.
As an example of formal language, an alphabet might be {a, b}and a string over that alphabet might be “ababba”

Automata Step by Step

Let’s see the definitions of “String”, “Alphabet”,” Sequence” and “Language”. Remember all above terms are connected. You can’t understand any of them without knowing the definitions of all of them.

String:

In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. These symbols are chosen from a predetermined set.

Example: Empty String (contains no symbols)

Length of Empty String is zero.

Now we will define “Alphabet”.

Alphabet:
An alphabet is a finite set of symbols.
Examples:
Binary Alphabet = {0, 1}
Unary alphabet= {1}
ASCII Alphabet= {…..A, B, C………, a, b, c…………}
Decimal Alphabet= {0, 1, 2…….8, 9}

Automata Step by Step

Formal Grammar:

A formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. The two main categories of formal grammar are that of generative grammars, which are sets of rules for how strings in a language can be generated, and that of analytic grammars, which are sets of rules for how a string can be analyzed to determine whether it is a member of the language. In short, an analytic grammar describes how to recognize when strings are members in the set, whereas a generative grammar describes how to write only those strings in the set.

Now it is necessary to understand the definitions of “String”, “Alphabet”,”Sequence” and “Language”. I will discuss them in the next Post.

Automata Step by Step

This post is connected to the previous post. So if you have not read that post, please give few minutes in reading that post.

Parsing:

Parsing (more formally syntax analysis) is the process of analyzing a sequence of tokens to determine its grammatical structure with respect to a given formal grammar. A parser is the component of a compiler that carries out this task.

Parsing transforms input text into a data structure, usually a tree, which is suitable for later processing and which captures the implied hierarchy of the input. Lexical analysis creates tokens from a sequence of input characters and it is these tokens that are processed by a parser to build a data structure such as parse tree or abstract syntax trees.

Can you guess what the next question is? Yes, you are right. Next question is what the Formal Grammar is.

Automata Step by Step

I am writing this blog for the people who are strongly interested in Automata and Formal languages or who want to start from basics of Automata.

First of all, we will discuss some very basic definitions of Automata. In Automata theory, all things are related to each other so you will notice that you need definitions of other words for understanding a particular definition. We will also see formal definitions of all terms after understanding their basic definitions. After basic and formal definitions, we will solve a lot of good “Problems of Automata” and see a lot of good examples.

Basic Definitions:

If you are a beginner, you should know what is Automata and Automata theory.

1. Automaton:
In Simple Words, An automaton (plural: automata) is a self-operating machine. The word is sometimes used to describe a robot, more specifically an autonomous robot. Used colloquially, it refers to a mindless follower.

An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, 'jumps' through a series of states according to a transition function (which can be expressed as a table). In the common "Mealy" variety of FSMs, this transition function tells the automaton which state to go to next given a current state and a current symbol.

2. Automata theory:

Automata theory is the study of abstract machines and problems they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.

Now at this point, it is important to know about Finite state machines.

3. Finite state machine (FSM):

A finite state automaton (plural: automata) is a model of behavior composed of a finite number of states, transitions between those states, and actions.

4. States:

A state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers.

We will see the definition of parser in the next post. Above 4 definitions are enough for today. Please don’t forget to review them otherwise you will not be able to understand the next post. Read carefully. Have a good day.