Hello everyone! This article is the second chapter on the series “Exploring Automata Theory” that I am publishing on. In this article, I will be equipping you with some of the basic terms, notations and their meanings in the automata theory. Upon learning them, you will be able to take your first step into learning this fascinating subject.
You might not able to quickly understand why we are learning these but as you move on further, you will be able to understand their significance. Just for now, learn that these are the tools with which you can master this skill. Okay, now let’s get started.
Basic Definitions :
- Symbol : Anything that is used to represent an object can be thought of as a symbol. For example, the letters a,b,c , the numerals 0,1,2 and so on can be seen as symbols.
- Alphabet : An alphabet is denoted by the symbol Σ. It is defined as a collection of symbols. For example, {a,b}, {d,e,f,g}, {0,1,5}. The idea behind a “collection” is simply a notion of a bunch of mathematical objects which are collected into one big pile. Think of it as a big bin full of trash, diamonds and empty bottles of beer, it doesn’t have to make sense what is in this collection, it’s just a collection.
- String : A sequence of symbols is known as a string. A sequence can be thought of as a list of elements with a particular order and repetitions allowed. For example, the list a, b, 0, 1, aa, ab, a0, a1,… denotes a string.
- Language : A language is defined as a set of strings.
An example to wrap up all the above definitions :
Consider the alphabet Σ = {0, 1}. Here 0 and 1 are your symbols. Let L1 denote the set of strings that are of length 2.
What are all the possible strings of length 2 ? The possible answers are 00, 01, 10, and 11. Here each of them i.e 00 denote a string ( because it is a sequence of 0’s and 1’s ).
Therefore, L1 = { 00, 01, 10, 11 } is the language over these alphabets.
Powers of Σ :
Let Σ = { 0, 1 }. We define the various powers of Σ as follows :
Σ⁰ : It denotes the set of all strings that are of length 0.
Σ⁰ = { ε } , where ε denotes the epsilon symbol.
Σ¹ : It denotes the set of all strings that are of length 1.
Σ¹ = { 0, 1 }
Σ² : It denotes the set of all strings that are of length 2.
Σ²= { 00,01, 10, 11 }
Σⁿ : It denotes the set of all strings that are of length n.
Σ* : It denotes the set of all possible strings of all lengths over {0,1} i.e Σ* = Σ⁰ U Σ¹ U Σ² U ….. U Σⁿ U ….
Cardinality :
It defines the number of elements present in the given set. For example, if Σ = { 0, 1 } then the cardinality of Σ² is 4, since 4 strings are present in the set.
REFERENCES :
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman-Introduction to Automata Theory, Languages, and Computations-Prentice Hall (2006)
If you liked this article, do share it with your friends and don’t forget to give claps. If you did not, then I am happy to hear your thoughts and suggestions. Any type of feedback and questions are most welcome. Do provide them in the comments section below.
