Important Notes on Theory of Computation for NET/SET/GATE

Important Notes on Theory of Computation for NET/SET/GATE

Theory of computation is one of the important papers mostly asked in UGC NET/SET and GATE qualification papers. The TOC subject is very vast and it is hard for someone to complete the entire syllabus. But for qualifying for the NET/SET or GATE exam, students don’t need to learn the entire subject. Students should only focus on key points of TOC which are mostly asked in such type of examination.

Below are many such important and key points/notes for the TOC paper. These notes are only for those students who already studied this paper but could not find keynotes that mostly asked for NET/SET/GATE exams.

Formal Language:

  • The collection of Strings; the language which has proper alphabets, grammar, and model (automata) is a Formal Language.
  • There are two types of Formal Language, Natural Language (NLP) and Artificial Language (AI).
  • In Formal Language, we give importance only to the Information of the string rather than the meaning of a string.

Grammar:

  • The collection of rules which are used to generate the strings is known as Grammar.
  • Grammar is generating device.
  • Types of formal grammar are shown in the table.
TypeGrammarLanguageModel
Type 0Recursive Enumerable Grammar (REG)Recursive Enumerable Language (REL)Turing Machine (TM)
Type 1Context Sensitive Grammar (CSG)Context Sensitive Language (CSL)Linear Bounded Automata (LBA)
Type 2Context Free Grammar (CFG)Context Free Language (CFL)Push Down Automata (PDA)
Type 3Regular Grammar (RG)Regular Language (RL)Finite Automat (FA)
  • All rules in Type 3 are in Type 2, Type 1, and Type 0.
  • All rules are in Type 2 are in Type 1, and Type 0 NOT in Type 3.
  • Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0 (according to Chomsky Hierarchy).

Automata Models:

  • The mathematical representation of formal language is called an automaton.
  • Automata is a recognizing or accepting device.
  • The automata which accept more number of language is more powerful.
  • Push Down Automata are more powerful than Finite Automata.
  • Linear Bounded Automata are more powerful than PDA and FA.
  • Turing Machine is more powerful than LBA, PDA, and FA.
  • There are two types of Finite Automata: DFA (Deterministic Finite Automata), and NFA (Non-deterministic Finite Automata).
  • DFA is more efficient than NFA.
  • Accepting the power of DFA = Accepting the power of NFA (rough idea).
  • Finite automata have a static and limited amount of memory. Because of this many FA cannot accept some of the simple formal languages.
  • Finite Automata + 0 Stack = Finite Automata
finite-automata
  • Finite Automata cannot accept the language L in Example 2 since apart from processing the input stream, we need to maintain the count between a’s and b’s. One extra memory element is required.
  • So, Finite Automata + 1 Stack = Push Down Automata (PDA) can accept the language in example 2.

Push Down Automata (PDA)

  • There are two types of PDA: DPDA (Deterministic PDA), and NPDA (Non-deterministic PDA).
  • For every Context Free Language (CFL) we can construct NPDA.
  • DPDA is more efficient than NPDA.
  • Accepting the power of DPDA ≠ accepting the power of NPDA.
  • E(NPDA) > E(DPDA)
  • NPDA is more powerful than DPDA.
  • Example:
    L = {an, bn, cn | n ≥ 1 }
       = {abc, aabbcc, …}
  • Push Down Automata (PDA) cannot accept the language L in the above example since it requires too many elements to maintain the code between a’s and b’s and b’s and c’s.
  • PDA + 1 Stack or FA + 2 Stacks = Turing Machine.
  • FA + 1 Tape = Turing Machine

Linear Bounded Automata (LBA)

  • There are two types of LBA: DLBA (Deterministic LBA) and NLBA (Non-deterministic LBA).

Turing Machine (TM)

  • There are two types of TM: DTM (Deterministic TM) and NDTM (Non-deterministic TM).
  • E(DTM) = E(NDTM)
  • DTM is more efficient than NDTM.
  • The power of Automata is shown in the table.
Least PowerfullMost Powerful
FA (DFA = NFA)DPDANPDALBATM

The Model has three types:

  1. Language Acceptor
  2. Computing Model
  3. Language Generator
AutomataModel
Finite AutomataLanguage Acceptor, Computing Model
Push Down AutomataLanguage Acceptor
Turing MachineLanguage Acceptor, Computing Model, Language Generator

String:

The sequence of symbols from the alphabet ∑ is called as a string. E.g. ∑ = {0, 1}, then

w = 01
w = 101
w = 10010

The length of string w is denoted by |w|.

Empty string: A string of length zero or a string without any symbol is called an empty string and it is denoted by ε (epsilon).

Concatenation of ε.

  1. w . ε = w = ε . w
  2. ab . ε = ab = ε . ab
  3. ε . ε = ε

Substring: Let u, w is the two substrings from the alphabet ∑. Then u is said to be substring of w if u occurs in w as it is in the safe order.

  1. If u is a substring of w, then |u| ≤ |w|.
  2. Every string is substring to itself.
  3. Every string ε is a substring for every string.

Types of Substring:

  1. Trivial or Improper Substring: If w is any string define over the alphabet ∑, then the substring w itself and Epsilon (ε) is called as trivial substrings.
  2. Non-Trivial or Proper Substring: If w is any string define over the alphabet ∑, then any substring of w other than w itself and empty string ε is called a non-trivial substring.

If w is any string with distinct symbols and |w| = n then total number of substrings = ∑ n + 1 = n*(n+1)/2 + 1.

Prefix: The sequence of starting symbol is called prefix.

Suffix: The sequence of ending symbol is called suffix. Example: w = ACE.
Prefix: ε, A, AC, ACE
Suffix: ACE, CE, E, ε

If w is any string with |w| = n then the number of prefix = number of suffix = n + 1.

Every prefix and suffix must be a substring but every substring need NOT be a suffix or prefix.

Trivial substrings are both prefixes as well as suffixes.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top