Introduction to Theory of Computation

This subject is divided into 3 main parts :

• Automata and languages
• Computability theory
• Time complexity

Automata: Study of abstract computing devices or machines.

Symbol: It is an abstract entity (letters and digits)

• Example: 0,1

Alphabet (∑): An alphabet may be defined as a finite, non-empty set of symbols.

• Example: Binary alphabet ∑ = {0, 1}

String: It is a sequence of symbols.

• Example: 0101 is a string

Finite String: Finite String is said to be a finite sequence of symbols.

• Example: 010 is a finite string that has a length of 3.

Infinite String: Infinite sequence of symbols.

• Example: 011111… is an infinite string that has infinite length. (infinite strings are not used in any formal language)

Language: A language is defined as a collection of sentences of finite length and all are constructed from a finite alphabet of symbols.

• Example: L = {00, 010, 00000, 110000} is a language over input alphabet ∑ = {0, 1}

Formal Language:  Formal language is defined as a language that is restricted to be designed from a set of finite alphabets.

Example:

• Set of all strings where each string starts with 1 over a binary alphabet.
• L={1, 10, 11, …} over 0’s and 1’s.

Empty String (Λ or ε or λ): If the length of the string is zero, so such string will be known as a void string or an empty string.

Kleene Closure

• If ∑ is the Alphabet, then there is a language in which any string of letters  ∑ is a word, even the null string. We call this language closure of the alphabet.

• It is denoted by * (asterisk) after the name of the alphabet is ∑^*. This notation is also known as the Kleene Star.
• If ∑ = {a, b}, then ∑^* = {ε, a, b, a, ab, bb,….}

∑^* = ∑⁰ ∪ ∑¹ ∪ ∑² ∪ …

∑^* = ∑⁺ ∪ {ε}

Positive Closure:

• The’ +’ (plus operation) is sometimes called positive Closure.
• If ∑ = {a}, then ∑⁺ = {a, aa, aaa, …}  = the set of nonempty strings from ∑

∑⁺ = ∑^* – {ε}

 

Concatenation of two strings:

• If x, y ∈ ∑^*, then x concatenated with y is the word formed by the symbols of x followed by the symbols of y.
• This is denoted by x.y, it is the same as xy.

Substring of a string:

• A string v is a substring of a string ω if and only if there are some strings x and y such that ω = xvy.

Suffix of a string:

• If ω = xv for some string x, then v is suffix of ω.

Prefix of a string:

• If ω = vy for some string y, then v is a prefix of ω.

Reversal of a string:

• Given a string ω, its reversal denoted by ω^R is the string spelt backwards.

Grammar:

• It enumerates strings of the language. It is a finite set of rules defining a language.
• A grammar is defined as 4-tuples (V_N, ∑, P, S),
• where, V_N is a finite non-empty set of non-terminals, ∑ is a finite non-empty set of input terminals, P is a finite set of production rules, and S is the start symbol.

Chomsky Hierarchy

The Chomsky hierarchy consists of the following four types of classes.

Type 0 Grammar (Unrestricted Grammar):

• These are unrestricted grammars which include all formal grammars.
• These grammars generate exactly all languages that can be recognized by a Turing machine.
• Rules are of the form α → β,
• where, α and β are arbitrary sequences of terminals and non-terminals and α ≠ ∧ (null).

Type 1 Grammar (Context Sensitive Grammar):

• Languages defined by type-1 grammars are accepted by linear bounded automata.
• Rules are of the form X → Y, where, X, Y ∈(V_N ∪ ∑)^*, and Length of X is less than or equal to the length of Y.

Type 2 Grammar (Context-free Grammar):

• Languages defined by type-2 grammars are accepted by push-down automata.
• Rules are of the form A → α, where, A ∈V_N , and α∈(V_N ∪ ∑)^*

Type 3 Grammar (Regular Grammar):

• Languages defined by type-3 grammars are accepted by finite-state automata.
• Regular grammar can follow either right linear or left linear.
• Right linear rules are of the form: A → α | αB where, A, B ∈ V_N and α∈∑*.
• Left linear rules are of the form: A → α | Bα where, A, B ∈ V_N and α∈∑*.

Type-0 Class is also called as:

• Unrestricted Grammars
• Recursively Enumerable Languages
• Turing Machine

Type-1 Class is also called as:

• Context-Sensitive Grammars
• Context-Sensitive Languages
• Linear Bound Automata

Type-2 Class is also called as:

• Context-Free Grammars
• Context-Free Languages
• Push Down Automata

Type-3 Class is also called as:

• Regular Grammars
• Regular Languages
• Finite Automata