Select Page

What is Automata Theory?

Automata theory is used to study the abstract machine and automata (the self-acting machine).  Abstract machine is a theoretical model of a computer used in Automata theory. Automata theory is used to solve the computational problems. Abstract devices are easiest models of real calculations or computations. The basic meaning of “Automata” means “self-making” which is taken from the word “αὐτόματα”. Automata used in various fields like:

• Theory of computation
• Compiler construction
• Artificial intelligence,
• Parsing

The basic terminologies used in Automata Theory

• Alphabets
• Strings
• Languages
• Grammars

Alphabets:

An alphabets is a finite set of non-empty symbols. The symbol ∑ (sigma) is used to denote an alphabet.

Examples:

∑ = {0, 1} is the binary alphabet

∑ = {a, b, c… z} is the set of lowercase letters

∑ = {A, B, C… Z} is the set of uppercase letters

Σ= {(, )}: the set of open and closed brackets

Strings:

A string is a finite sequence of symbols selected from alphabets.

Examples:

abcbz is a string over Σ = {a, b, c, d… z}

11001011 is a string over Σ = {0, 1}

)) ()(() is a string over Σ = {(,)}

Kleene Star (Closure)

The Kleene star ∑* includes the all possible strings of lengths over  including the empty string λ or ε. It is represented by using below notation:

∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. ∑n

Example:

∑ = {1, 2}

∑* = {λ, 1, 2, 11, 22, 12, 21…}

Kleene Star (Plus)

The set + is the infinite set of all possible strings of lengths over ∑ excluding λ or ε. In simple words it does not include empty string.

It is represented by using below notation:

+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….∑n

+ = ∑* − {ε}

Example

∑ = {1, 2}

+ = {1, 2, 11, 22, 12, and 21…}

Empty or Null String

The strings having no symbol is called the empty string and null string. Empty string is the string with zero or no occurrence of symbols in the given string. The general notation of representing empty string is ε.

Reverse of String

The reverse of string WR is calculated by writing symbols in reverse order.

Example

“automata” is the string

WR = “atamotua” is the reverse of string

Substring

A string of consecutive characters from W is called as substring of W.

Example

W = bbababa be a string over an alphabet Σ = {a, b} then a, bba, aba are substrings of w.

Length of String

The number of symbols in a string defines the length of the string. Length of a string w, denoted by “|w|”, is equal to the number of (non- ε) characters in the string.

Example:

W = 010100

No of string |W| = 6

Concatenation of Strings

The Concatenation of Strings is used to join and concatenate the two or more strings. Suppose ‘a’ and ‘b’ are the strings, then Concatenation of strings will be ‘ab’.

Example:

“Hello” is a string and “World” is another string

The Concatenation of Strings is HelloWorld

Palindrome String

A palindrome is the string which is same as whether it is written forward or backward.

Examples:

Madam is a palindrome string

131 is a palindrome string

Language

A language is a set of strings or symbols from some alphabet. A language is collection of strings. A language can be finite or infinite also.

Examples:

The language L of strings of length 2, defined over Σ= {a, b, c}, can be written as

L= {aa, ab, ac, ba, bb, ac, ca, cb, cc}

The complement of language is denoted by L’, it is calculated by using

L’ = Σ* – L.

Grammar

A grammar defines a set of rules, and with the use of these rules, valid sentences in a language are generated. Similar to English language we have set of rules in automata, which help us in creating sentences. A popular way to derive a grammar recursively is phrase-structure grammar.

Example