Theory of Computation – Basic Definitions

This section describes the terms that are frequently used in the theory of computation and automata theory. Before proceeding to the next section section you should understand the terms that are described below as they are used in most of the concepts in the theory of computation.

Theory of computation is entirely based on symbols. These symbols are generally letters and digits.
Alphabets are defined as a finite set of symbols.
∑ = {0, 1} is an alphabet of binary digits
∑ = {A, B, C, …., Z} is an alphabet.

A string is a finite sequence of symbols selected from some alphabet. It is generally denoted as w.For example for alphabet ∑ = {0, 1} w = 010101 is a string.

Length of a string is denoted as |w| and is defined as the number of positions for the symbol in the string. For the above example length is 6.

The empty string is the string with zero occurrence of symbols. This string is represented as є or λ.

The set of strings, including the empty string, over an alphabet ∑ is denoted by ∑*.
For ∑ = {0, 1} we have set of strings as ∑* = {є, 0, 1, 01, 10, 00, 11, 10101,…}.
and ∑1 = {0, 1} , ∑2 = {00, 01, 10, 11} and so on.


∑* contains an empty string є. The set of non- empty string is denoted by ∑+. From this we get:
∑* = ∑+ U {є }

Concatenation of strings
Let w1 and w2 be two strings then w1w2 denotes their concatenation w. The concatenation is formed by making a copy of w1 and followed by a copy of w2.
For example w1 = xyz, w2 = uvw
then w = w1w2 = xyzuvw
Also w13 = w1w1w1

A language is a set of string all of which are chosen from some ∑*, where ∑ is a particular alphabet. This means that language L is subset of ∑*. An example is English language, where the collection of legal English words is a set of strings over the alphabet that consists of all the letters. Another example is the C programming language where the alphabet is a subset of the ASCII characters and programs are subset of strings that can be formed from this alphabet.

Concatenation of Languages
If L1 and L2 are two languages then their concatenation can be defined as :
L = L1 . L2 where L = {w: w = xy where x є L1, y є L2}
It means that all the strings in the language L are concatenation of stings of language L1 and L2

Kleen Closure
If S is a set of words then by S* we mean the set of all finite strings formed by concatenating words from S, where any word may be used as often we like, and where the null string is also included.

S* is the Kleen closure for S. We can think of kleen star (S*) as an operation that makes an infinite language of strings of letters out of an alphabet.
For example for ∑ = {a}
∑* = {є, a, aa, aaa, ….}


Finite Automata
They are the devices that accept the generated language. They take as input a string and produce the output as ‘yes'(accepted) or ‘no'(rejected). This makes them different from the transducers which take as input a string and generates another string. In the future tutorials we are going to discuss about various automata (singular automaton).

These machines are very similar to Central Processing Unit of a computer but absence of memory makes them more restricted. Computers are deterministic. They can only be in one state at a given moment. Finite automata can be either deterministic or nondeterministic.

A finite automata consists of 3 components – an input tape, a reading head and a finite control system. Reading head reads the input from the input tape and the finite control system decides the action. The finite control system begins at the initial state and may or may not change state on the given input.If after reading the input string the machine winds up in one of final states the input string is considered accepted else it is rejected.
Finite Automata
A finite automata is called finite because there are finite number of states it can exist in and also the number of possible input symbols are also finite.The change of state is governed by the input.


Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.
If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.