Syllabus of Theory Of Computation ( TOC )

There are six important topics of theory of computation are as follows :

•  Language
•  Automata
•  Context-Free Language ( CFL ) and Context-Free Grammar ( CFG )
•  Recursive Language ( REC) and Recursively Enumerable Language ( RE )
•  Closure Properties of Regular Language
•  Decidability and Undecidability

1. Language

A symbol is the smallest unit of a language. A symbol is a single character, such as 0, 1, 2, 3, a, b, c, … . A finite set of symbols is called an alphabet (Σ). Symbols serve as a building blocks of strings. String are used to form a language. A regular language is a language that can be described by a regular expression or recognized by a finite automaton ( FA ).

Symbol : The smallest unit of the language, such as 0,1, a, b, c, etc.

Explanation: The diagram shows the relationship between an alphabets and it’s symbols in TOC. Σ (Sigma) represents an alphabet notation while the elements inside the curly braces or { } is called a symbol.

Alphabet (Σ) : A finite collection of symbols, such as {a, b}.

Explanation: The diagram shows the relationship between an alphabets and it’s symbols in TOC. Σ (Sigma) represents an alphabet notation while the elements inside the curly braces or { } is called a symbol.

• String : A finite sequence of symbols taken from an alphabet or A collection of sequence, such as a, b, ab, ba, aa, bb, aab, … . There are two types of strings are as follows.
• Valid String
• Invalid String

Types of String

1. Valid String

A valid string is a sequence of symbols in which every symbols belongs to the specified alphabet (Σ). If the string contain only the symbols defined in the alphabet, it is considered valid.

Examples

• If Σ = {0,1} : 0, 01, 1101, 11010, … are valid strings because they contain only 0 and 1.
• If Σ = {a, b} : a, aaab, bbbba, ababba, ….. are valid strings because every symbols belong to the alphabet.
• If Σ = {0,1,2,3,…,9} : 12345, 56653, 11288, 12890, … are valid strings since they use only digits from 0 to 9.
• If Σ = {a, b, c, d, …, z} : hello, beautiful, theory, … are valid strings because all character are lowercase English letters.

Explanation: The diagram shows the valid strings in which, every symbols belong to the specified alphabet Σ.

2. Invalid String

An invalid string contains one or more symbol that are not included in the given alphabet ( Σ ). Even a single invalid symbol make the entire string invalid.

Examples

• If Σ = {0,1} : 012, 102, 2 and 10b are invalid strings because 2 and b are not part of the alphabet.
• If Σ = {a, b} : abc, acb, a1b, and cab are invalid strings because c and 1 are not included in the alphabet.

Explanation: The diagram shows the invalid strings in which, even a single invalid symbol make the entire string invalid.

Other Examples

• If the Length of string is 2 than : {aa, ab, ba, bb, …}
• If the Length of string is 3 than : {aaa, aab, aba, abb, baa, bbb, …}

Language : A set of valid strings formed from an alphabet or A collection of all possible strings, such as {aⁿ | n ≥ 0}, {a, aa, aaa, …}, etc. There are two most important types of language are as follows.

• Finite Language
• Infinite Language

Explanation: This table shows different examples of the Languages formed from the alphabet Σ = {a, b}. It also shows the number of strings in each Language.

Types of Language

1. Finite Language

A finite language is a language that contains a limited ( finite ) number of strings.

Example

• Σ = {0,1}
• L = {0, 01, 10, 11}

Since, the language contains only four strings, it is a finite language.

Explanation: This table shows different examples of the Finite Languages. It list the strings in each Finite Language and gives a brief explanation of every example.

2. Infinite Language

An infinite language is a language that contains an unlimited ( infinite ) number of strings.

Example

• Σ = {0, 1}
• L = {0, 00, 000, 0000, …}

Since the number of strings is unlimited, it is an infinite language.

Explanation: This table shows different examples of the Infinite Languages. It list the strings in each Infinite Language and gives a brief explanation of every example.

Note: A symbol is a single character, where as an alphabet (Σ) is a finite collection of symbols. Understanding this difference is essential in the theory of computation ( TOC ).

2. Automata

An automation is an abstract model of a digital computer. It is a mathematical model or machine used in the theory of computation. It is used to solve the problem. It means that string is the part of the language or not. In simple words, an automaton checks if a string is accepted or rejected according or using the rule of the language. There are four main types of automata in theory of computation.

• Finite Automata ( FA )
• Pushdown Automata ( PDA )
• Linear Bounded Automata ( LBA )
• Turing Machine ( TM )

1. Finite Automata ( FA )

Finite Automata ( FA ) cannot accept the language that require temporary storage because it does not have any memory or stack to store symbols while processing the input string. It is accept only regular language. Therefore, finite automata can recognize only the regular language. Finite Automata ( FA ) having a limited power. It is less powerful than Pushdown Automata ( PDA ), Linear Bounded Automata ( LBA ) and Turing Machine ( TM ). There are two types of Finite Automata are as follows.

• Deterministic Finite Automaton ( DFA )
• Non-Deterministic Finite Automaton ( NFA )

Example

L = {aⁿ ∣ n ≥ 1}

Symbols Table in Finite Automata

Symbols table in finite automata are as follows.

Types of Finite Automata ( FA )

1. Deterministic Finite Automaton ( DFA )

In Deterministic Finite Automaton ( DFA ), every input symbol is only one possible next state.

Example

Explanation: The automaton starts at q₀. Each input has only one input next state, so it is called a Deterministic Finite Automaton ( DFA ).

2. Non-Deterministic Finite Automaton ( NFA )

In Non-Deterministic Finite Automaton ( NFA ), single input symbols may have more than one possible next state.

Example

Explanation: The automaton starts at q₀. On input a, it can move to q₀ or q₁, So it is called a Non-Deterministic Finite Automaton ( NFA ).

Note: This language include all strings of ‘a’ whose length is greater than 1, such as: aa, aaa, aaaa, aaaaaa, …

2. Pushdown Automata ( PDA )

Pushdown Automata ( PDA ) is an automaton that uses a only one stack as temporary memory while processing an input string. This extra memory allows PDA to recognize language that cannot be recognized by finite automata ( FA ). It is accept only Context-Free Languages ( CFLs ). Therefore, PDA is used to recognize Context-Free Languages ( CFLs ).

Example

PDA = FA + 1 Stack

Note: 1 Stack means that Pushdown Automata ( PDA ) has one stack as a temporary memory.

3. Linear Bounded Automata ( LBA )

LBA is actually a Turing Machine ( TM ) with a limited tape. The size of the tape is restricted according to the length of the input string. in simple words, the  We have to limit input output tape. based on input size input tape is bounded based on the input size. LBA accepts only Context- Sensitive Languages ( CSLs ). It is more powerful than Finite Automata ( FA ) and Pushdown Automata ( PDA ) but less powerful than a Turing Machine ( TM ).

Example

L = {aⁿbⁿcⁿ ∣ n ≥ 1}

Note: This language contains string in which the number of a, b, and c are equal, such as abc, aabbcc, aaabbbccc, …

4. Turing Machine ( TM )

A Turing Machine ( TM ) is a mathematical model of computation. It is used to solve the problems that require more memory and more comparisons than a Finite Automaton ( FA ) or a Pushdown Automaton ( PDA ). Turing Machine ( TM ) accepts only a Recursively Enumerable ( RE ) Language. Therefore, TM is more powerful than FA, PDA and LBA.

Formal Definition

M = (Q, Σ, Γ, δ, q₀, B, F)

Components of Turing Machine

Q : Set of finite state it means that the number of states are always finite, such as {q₀, q₁, q₂, q₃, …}.

Σ ( Sigma ) : Input alphabet. It contains the input symbols, such as {0,1}.

Γ ( Gamma ) : Tape alphabet. It contains all input symbols and some extra symbols used during computation, such as {0,1,X,Y,B}. Where X and Y are extra symbols and B is the blank symbols.

Note: Σ ⊆ Γ ( Sigma is a subset of Gamma )

δ ( Transition Function ) : Read the current state, tape symbols and change to the next state.

q₀ : is an initial state.

B : B denotes the blank symbol.

F : Set of final or accepting states.

Note: All of these sets are finite.

Transition Function

The transition function of a Turing Machine are as follows.

δ : Q × Γ → Q × Γ × {L, R}

Examples

Q = {q0, q1, q2, qf}

Γ = {0, 1, X, Y, B}

3. Context-Free Language ( CFL ) and Context-Free Grammar ( CGL )

Context-Free Language ( CFL )

A Context-Free Language ( CFL ) is a language that can be generated by a Context-Free Grammar ( CFG ). These languages are more powerful than regular language. A Pushdown Automata ( PDA ) is used to recognize Context-Free Language.

Example

• {aⁿcⁿ ∣ n ≥ 1}

Context-Free Grammar ( CGL )

A Context-Free Grammar ( CFG ) is a set of rules used to generate a Context-Free Language ( CFG ). A CFG consist of four components are as follows.

Components of CFG

G = {V, T, P, S}

Where, V = Set of variables or non terminal symbols ( Uppercase Letters )

Example: {A, B, C}

T = Set of terminal symbols ( Lowercase Letters or digits )

Example: {a, b, c, 5, 7}

P = Production Rule or Set of Production that defines how variables are replaced.

Example: P = {S → aSb, S → ab}

S = Start symbol from which the grammar begins.

Example: S

Note: All these sets are finite.

Production Form

Production Form of CFG are as follows.

A → α

Where,

• A is a single non-terminal symbol (A ∈ V).
• α is a string of terminals and/or non-terminals [α ∈ (V ∪ T) ].

Examples

• S → aSb
• A → α
• A → ε

Here, ε (epsilon) represents the empty string.

4. Recursive Language ( REC) and Recursively Enumerable Language ( RE )

Recursive Language ( REC )

A Recursive Language ( REC ) is a language that is accepted  by a Halting ( Total ) Turing Machine ( TM ). The Turing Machine always stops for every input and gives a clear answer such as Accept or Reject.

Properties

There are three properties of Recursive Language ( REC ) are as follows.

• Accepted by a Halting or Total Turing Machine ( TM )
• The machine are always stop for every input.
• Recursive language are closed such as union, intersection and compliment.

Possible States

There are two possible states of Recursive Language ( REC ) are as follows.

• Halt and Accept
• Halt and reject

Note: A recursive Turing Machine ( TM ) never runs forever.

Recursively Enumerable Language ( RE )

A Recursively Enumerable Language ( RE ) is a language that is accepted  by a Turing Machine ( TM ). If the input belongs to the language, the machine accepts it and if the input does not belong to the input, the machine may reject.

Properties

There are three properties of Recursively Enumerable Language ( RE ) are as follows.

• Accepted by a Turing Machine ( TM )
• The machine always accepted by a valid string.
• Recursively Enumerable Language ( RE ) are closed under many operations except compliment.

Possible States

There are three possible states of Recursively Enumerable Language ( RE ) are as follows.

• Halt and Accept
• Halt and reject
• Never Halt or Infinite Loop

Note: REC are always stops ( Accept or Reject ) and RE may not stop for some rejected strings.

5. Closure or Closed Properties of Regular Language

A regular language remains regular even after applying certain operations on it. These operations are called Closure or Closed Properties. There are many Closure or Closed Properties are as follows.

• Union (L₁ ∪ L₂)
• Concatenation (L₁L₂)
• Kleene Star (L*)
• Complement (L̅)
• Intersection (L₁ ∩ L₂)
• Difference (L₁ − L₂)
• Reversal (Lᴿ)
• Homomorphism
• Reverse Homomorphism
• Quotient Operation
• INIT ( Initial Operation )
• Substitution
• Infinite Union

1. Union (L₁ ∪ L₂)

If L₁  and L₂ are regular languages, then their union is also a regular language. It means that combine all strings of both language.

2. Concatenation (L₁L₂)

If L₁  and L₂ are regular languages, then joining their strings one after another gives a regular language. It means that first take a string from L₁, then attach a string from L₂.

3. Kleene Star (L*)

If L is regular language, then L* is also regular language. It means that strings of L can be repeated zero or more times.

4. Complement (L̅)

The complement of a regular language is also regular. It means that it contains all strings not present in the language.

5. Intersection (L₁ ∩ L₂)

If L₁  and L₂ are regular languages, then their intersection is also regular. It means that it contains only those strings that are common in both language.

6. Difference (L₁ − L₂)

The difference of two regular language is also regular. It means that it contains those strings that are in L₁ but not in L₂.

7. Reversal (Lᴿ)

The reverse of a regular language is also regular. It means that every string is written in the opposite or reverse order.

Example: abc → cba

8. Homomorphism

When applying a homomorphism regular language remain regular. It means that each symbol or string are replaced with another symbol or string.

9. Reverse Homomorphism

The reverse homomorphism of a regular language is also regular. It means that homomorphism is applied when, it finds out original strings.

10. Quotient Operation

The quotient operation of a regular language is also regular. It means that it removes the suffix or prefix from strings according to the language.

11. INIT ( Initial Operation )

Regular language are closed under the INIT ( Initial Operation ). It means that it contains all prefixes or starting parts of the strings.

Example: For abcd → ε, a, ab, abc, abcd

12. Substitution

In substitution replace every symbol using a regular pattern.

13. Infinite Union

Regular language are not closed under the Infinite Union. In simple words, combining an unlimited number of regular languages may produce a language that is not regular.

Note: A regular language remains regular after applying a most operations. However, it is not closed under the Infinite Union.

6. Decidability and Undecidability

Decidability

A problem is called decidable if an algorithm exist that always gives the correct answer and stops after a finite time. It means that decidability is a problem that can be a solved by an algorithm. The algorithm always gives the correct answer yes or no and stops after a finite number of steps. The decidability table are as follows.

Decidability Table

Step 01: The explanation of Decidability Table are as follows.

Regular Languages (REG): Decidable for all eight decision problem.

Deterministic Context-Free Languages (DCFL): Decidable only for membership, Emptiness, Infiniteness, Completeness and equality.

Context-Free Languages (CFL):  Decidable only for membership, Emptiness and Infiniteness.

Context-Sensitive Languages (CSL) and Recursive Languages (RE): Decidable only for membership.

Recursively Enumerable Languages (RE): Undecidable for all decision problem.

Undecidability

A problem is called undecidable if no algorithm exist that always stop and correctly determine the answer for every input.  It means that undecidability is a problem for which no algorithm that can  solve a problem correctly for every possible input.  Such problems do not have a decision procedure that always terminates with the correct answer. The undecidability table are as follows.

Step 01: The explanation of Undecidability Table are as follows.

Regular Languages (REG): Undecidable for all eight decision problem.

Deterministic Context-Free Languages (DCFL): Undecidable only for membership, Emptiness, Infiniteness, Completeness and equality.

Context-Free Languages (CFL):  Undecidable only for membership, Emptiness and Infiniteness.

Context-Sensitive Languages (CSL) and Recursive Languages (RE): Undecidable only for membership.

Recursively Enumerable Languages (RE): Decidable for all decision problem.