**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 W^{R} is calculated by writing symbols in reverse order.

**Example**

“automata” is the string

W^{R }= “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**

1 2 3 4 5 6 7 8 9 |
A derivation of “The girl sleeps” <Sentence> => <noun-phrase> <predicate> => <noun-phrase> <verb> => <article> <noun> <verb> => The <noun> <verb> => The girl <verb> => The girl sleeps |