Introduction of Theory of Computation

Amu_Ke_Fundye

Introduction of Theory of Computation

Automata: Study of abstract computing devices or machines.

Symbol: A symbol is an abstract entity i.e., letters and digits.

• Example: 0,1

Alphabet (∑): An alphabet is a finite, nonempty set of symbols.

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

String: It is a sequence of symbols.

• Example: 0101 is a string

Finite String: It is a finite sequence of symbols.

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

Infinite String: It is an infinite sequence of symbols.

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

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

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

Formal Language: It is a language where form of strings is restricted over given alphabet.

Example:

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

Empty String (Λ or ε or λ): If length of the string is zero, such string is called as empty string or void string.

Kleene Closure:

• If ∑ is the Alphabet, then there is a language in which any string of letters from ∑ 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 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 spelled 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 finite non-empty set of non-terminals, ∑ is finite non-empty set of input terminals, P is finite set of production rules, and S is the start symbol.

Chomsky Hierarchy: The Chomsky hierarchy consists of 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 sequence 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 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

Finite Automata (FA):

• Machines with fixed amount of unstructured memory, accepts regular languages.
• Applications of FA: useful for modeling chips, communication protocols, adventure games, some control systems, lexical analysis of compiler design, etc.

Pushdown Automata (PDA):

• Finite Automata with unbounded structured memory in the form of a pushdown stack, accepts context free languages.
• Application of PDA: useful for modeling parsing, compilers, postfix evaluations, etc.

Turing Machine (TM):

• Finite Automata with unbounded tape, accepts or enumerates recursively enumerable languages.
• Equivalent to RAMs, and various programming languages models.
• Applications of TM: Model for general sequential computation (real computer).

Regards
Amrut Jagdish Gupta