Prerequisite Before learning Theory of Automata 

After reading the following article we will have a basic understanding of the prerequisite required to learn the concept of the Theory of Computation.

Before we move to the Theory of Automata, we should have a basic understanding of some terminologies which are frequently used like Symbols, Alphabets, Strings, Languages.

Symbols : 

Symbols are indivisible objects or entities that cannot be defined. That is, symbols are the atoms in the world of languages. A symbol is any single object such as

1, a, b, #

Alphabets :

An alphabet is a finite, non-empty set of symbols that are normally denoted by Σ. When more than one alphabets are considered for discussion, then subscripts may be used (e.g. Σ₁, Σ₂ etc) or sometimes another symbol like G may also be introduced.

Example : 

        Σ = {0,1}

        Σ = {a, b, c}

        Σ = {a, b, c, &, z}

        Σ = {#,$, @, β, €, α}

Strings or Words over Alphabet :

A string or word over an alphabet Σ is a finite sequence of concatenated symbols of  Σ.

Example: 0110, 11, 001 are three strings over the binary alphabet { 0, 1 }. aab, abcb, b, cc are four strings over the alphabet { a, b, c }.

It is not the case that a string over some alphabet should contain all the symbols from the alphabet. For example, the string cc over the alphabet { a, b, c } does not contain the symbols a and b. Hence, it is true that a string over an alphabet is also a string over any superset of that alphabet.

Length of a string :

The number of symbols in a string w is called its length, denoted by |w|. Example : | 011 | = 4, |11| = 2, | b | = 1

Convention: We will use small case letters towards the beginning of the English alphabet to denote symbols of an alphabet and small case letters towards the end to denote strings over an alphabet.

That is, a,b,c ∈ Σ  (symbols) and u,v,w,x,y,z are strings.

Some String Operations : 

Let X=a₁a₂a₃ ∈ a_n and Y=b₁b₂b₃ ∈ b_m be two strings. The concatenation of x and y denoted by xy, is the string a₁a₂a_3...a_nb₁b₂b_3...b_m . That is, the concatenation of x and y denoted by xy is the string that has a copy of x followed by a copy of y without having any space between them.

Example: Consider the string 011 over the binary alphabet. All the prefixes, suffixes, and substrings of this string are listed below.

Prefixes: ε, 0, 01, 011.

Suffixes: ε, 1, 11, 011.

Substrings: ε, 0, 1, 01, 11, 011.

 Powers of Strings: For any string x and integer n ≥ 0, we use xⁿ to denote the string formed by sequentially concatenating n copies of x. We can also give an inductive definition of xⁿ as follows:

xⁿ ₌  e , if n₌ 0; otherwise xⁿ = xx^n-1.

for example  x=011, then x³=011011011, x¹=011, x⁰=e.

Powers of Alphabets: We write Σ^k  (for some integer k) to denote the set of strings of length k with symbols from Σ. In other words,

Σ^k = { w | w is a string over Σ and | w | = k}.

Hence, for any alphabet, Σ⁰ = {e} denotes the set of all strings of length zero. That is, Σ⁰ = {e}. For the binary alphabet {0,1} we have the following.

Σ⁰ = {e}

Σ¹ = {0,1}

Σ² = {00,01,10,11}

Σ³ = {000,001, 010,011, 100, 101, 110, 111}

The set of all strings over an alphabet Σ is denoted by Σ⁺ . That is,

             Σ⁺  = Σ⁰ U Σ¹ UΣ² U Σ³ U Σ⁴ .... U Σⁿ

The set contains all the strings that can be generated by iteratively concatenating symbols from any number of times.

Example : If Σ = { a, b }, then

          Σ⁺  = { ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …}.

Languages:

A language over an alphabet is a set of strings over that alphabet. Therefore, a language L is any subset of Σ ^ϕ. That is, L ⊆ Σ ^ϕ.

Example:

1.    F is the empty language.

2.    Σ ^ϕ is a language for any Σ.

3.    {e} is a language for any Σ. Note that, ϕ ≠ {e}. Because the language F does not contain any string but {e} contains one string of length zero.

4.    The set of all strings over { 0, 1 } containing an equal number of 0's and 1's.

5.    The set of all strings over {a, b, c} that starts with a.

Convention: Capital letters A, B, C, L, etc. with or without subscripts are normally used to denote languages.

Set operations on languages: Since languages are set of strings, we can apply set operations to languages. Here are some simple examples (though there is nothing new in it).

Union: A string x ϵ L₁UL₂ iff  x ϵ L₁ or x ϵ L₂

Example: { 0, 11, 01, 011 }U { 1, 01, 110 } = { 0, 11, 01, 011, 111 }

Intersection: A string, xϵ L1 ∩ L2 iff x ϵ L1 and x ϵ L2.

Example: { 0, 11, 01, 011 } { 1, 01, 110 } = { 01 }

Complement: Usually, Σ^ϕ is the universe that a compliment is taken with respect to that only.  For a language A, the complement is Ā.

Example: Let L = { x | |x| is even }. Then its complement is the language                             { x ϵ Σϕ | |x| is odd }.

Reversal of a language:

The reversal of a language L, denoted as L^R, is defined as:

L^R = {W^R | W ϵ L}.

Example : 1. Let L = { 0, 11, 01, 011 }. Then L^R = { 0, 11, 10, 110 }.

Let L = {  1ⁿ0ⁿ | n is an integer }. Then L^R { 1ⁿ0ⁿ | n is an integer }.

Language concatenation :

The concatenation of languages L₁ and L₂ is defined as

L₁L₂= { xy | x ϵ L₁ and  y ϵ L₂}.

Example : {a,ab}{b,ba} = {ab, aba, abb, abba}.

Note that,

·       L₁L₂ ≠ L₂L₁

·       Lϕ = ϕ

·       L{ε}= L= {ε}.

Iterated concatenation of languages :

Since we can concatenate two languages, we also repeat this to concatenate any number of languages. Or we can concatenate a language with itself any number of times. The denotes the concatenation of L with itself  n times. This Lⁿ is defined formally as follows:

L₀ = {e}

Lⁿ = L L^n-1

^Example :

Let L = {a,b}, Then according to definition,

L₀ = {e}

L₁= L(e) = L = {a, ab}

L₂ = LL₁ = {a, ab} {a, ab}= {aa, aab, aba, abab }

L₃ = LL₂ = {a, ab}{aa, aab, aba, abab }

                     {aaa, aaab, aaba, aabab, abaa, abaab, ababa, ababab}

and so on...

 

I hope now you have an understanding of basic terminologies which are required before moving the concept of automata.  If you have any suggestions let me know through comments.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.