Introduction of Theory of Computation

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

Amu_Ke_Fundye

Search This Blog