As an automata theory is a study of an abstract machine as well the computation problems that can be solved using them. So some mathematical preliminaries and component used to represent a machine behavior. Here we study about the leading notations and related terminology that are used in the computation process in study of theory of automata.

Before Starting it you can also read:

Alphabets:

An alphabet is a finite non empty set of symbols, which used to represent the input of a machine. Alphabets are typically thought of as represented by letters, characters, digits, signs, punctuation, etc. Conventionally we use the symbol ∑ for an alphabet. Common alphabets include:

  • ∑ = {0, 1}: The binary alphabets.
  • ∑ = {a, b, c, ……, z}: The set of all lower-case letters.
  • ∑ = {The sets of all ASCII characters or the set of all printable ASCII characters}.

An infinite sequence of letters may be constructed from elements of an alphabet as well.

Strings:

A string is a finite ordered sequence of symbols chosen form some set of alphabet or ∑. For example, ‘aababbbbaa’ is a valid string from the alphabet ∑ = {a, b}, similarly ‘001111000101’ is a valid string form the alphabet ∑ = {0, 1}.

Empty string:

Every alphabet ∑ has a special string called empty string which means the string with zero occurrences of symbols. This string represented by λ, e or ε. It is the string that may be chosen from any alphabet whatsoever.

Length of a string:

The finite occurrence of input symbols form ∑ present the length of a string. If s denotes the string over alphabet ∑ then length of a string is represented by |S|. For instance, ‘001110’ is a string from the alphabets ∑= {0, 1} has length 6. Similarly if ∑ = {a, b} and S = ‘aabbabbba’ then |S| = 9.

Note: The length of empty string | ε| = 0.

Power of an alphabet:

If ∑ is an alphabet, we can express the set of all strings of a certain length form that alphabet by using an exponential notation. We denoted it ∑n to be the set of strings of length n, each of whose symbols is in given input alphabet ∑.

For example: ∑0 = {ε} regardless of what alphabet ∑ is, i.e. ε is the only string whose length is zero.

If ∑ = {0, 1}, then ∑1 = {0, 1}, similarly ∑2 = {00, 01, 10, 11} or
3 = {000, 001, 010, 011, 100, 101, 110, 111} and so on.

Note: A slight cause in between ∑0 and ∑1. The former is an alphabet; its members 0 and 1 are symbols. The latter is a set of strings; its members are the strings 0 and 1, each of which is of length 1. We shall not try to use separate notations for these two sets, relying on context to make it clear whether {0, 1} or similar sets are alphabets or sets of strings.

Kleene star:

Kleene star is a unary operator introduced by Stephen Kleene. It is also called kleene operator and kleene closure. It is defined as the set of all possible strings of all possible lengths on alphabet ∑ including ‘ε’ (empty string). Kleene closure is represented by ∑* or L*. It is widely used for regular expressions.

Formal definition of Kleene Closure:

Given a set of S define over alphabet ∑;
S0 = {ε}
S1 = {S}
and define recursively the set
Si+1 = {uv : u ∈ Si and v ∈ S} for each i > 0
So according to Kleene closure definition;
S* = ∪iN Vi = {ε}∪S1∪ S2∪ S3∪ S4∪….
For example: Kleene star over alphabet ∑ = {0, 1},
L* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, .. .. .. .. ..}

Kleene plus:

Kleene plus defined as the set of all possible strings of all possible lengths on alphabet ∑ excluding ‘ε’ (empty string). In other words Kleene plus omits the S0 term form the kleene star string sets. Kleene plus is denoted by ∑+ or L+.

Formal definition of Kleene Plus:

Given a set of S define over alphabet ∑;
S1 = {S}
and define recursively the set
Si+1 = {uv : u ∈ Si and v ∈ S} for each i > 0.
So according to Kleene plus definition;
S+ = ∪iN Vi = S1∪ S2∪ S3∪ S4∪….
Conversely,  L* can be written as { ε }∪L1.
For example: Kleene plus over alphabet ∑ = {0, 1},
L* = {0, 1, 00, 01, 10, 11, 000, 001, 010, 011, .. .. .. .. ..}

Concatenation of strings:

Concatenation of strings is the technique to merging the symbols of strings together. Let A and B be two strings. Then AB denotes the concatenation of A and B, that is, the string formed by making a copy of A and following it by a copy of B. More precisely, if A is the string of composed of i symbol i.e. A = a1 a2 a3 .. .. .. ai and B is the string composed of j symbols i.e. B = b1b2b3.. .. .. bj.

For example: Let A = 11001 and B = 010. Then the concatenation of strings as follows;

AB = {11001010}, and
BA = {01011001}.
Note: Concatenating the string A with empty strings i.e. ‘ε’ is string A only. For example: εA = Aε = A.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.