Prerequisites before learning the Theory of Automata 

Introduction

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.

Know about 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, #

Know about 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}

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

Know about 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.

Know about the 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.

Know about 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.

Power 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.

Know about 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, …}.

Know about 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).

Know about 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 }

Know about Intersection: 

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

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

Know about 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 }.

Know about 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 }.

Know about 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= {ε}.

Know about 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…