Skip to content
THE CS NOTES

TOC Tutorial (GATE Wallah)

0. Introduction

Section titled “0. Introduction”
  • Decidable Problem - Problem for which Algorithm exist
  • Undecidable Problem - Problem for which no Algorithm exist.
  • Turing Machine Concepts is used to tell if Algorithm exist or Not for a problem

Theory of Computation :

  • Mathematical Study of Computing Machine and their Capability
  • or Study of Automata theory and formal Languages

Automata -> Mathematical Model or Theoretical Machine

  • Finite Automata -> Regular Language ⭐

  • Pushdown Automata -> Context-free Language ⭐

  • Linear-bounded Automata -> Context-sensitive Language

  • Turing Machine -> Recursive Enumerable Language

1. Finite Automata

Section titled “1. Finite Automata”

Finite Automata -> Mathematical model which contains finite numbers of states and transitions

                 Finite Automata
       ⬋                           ⬊


    Without output                 with output
    - DFA                        - Mealy machine
    - NFA                        - Moore Machine
    - ϵ-NFA
    -> Input -> Accept/Not?     ->Input->Output
    Ex: Use in Compiler       Ex:Use in Hardware

1.1 DFA

DFA/DEF -> Finite Automata in which from every state on every input symbol exactly one transition should exist

DFA is defined as
DFA = (Q, ∑, q₀, F, ∂ )
- Q : Fineite set of states
- ∑ : Input alphabet
- q₀: initial state
- F : Set of final states
- ∂ : Transition Function Q*∑ -> Q

DFA Detection Questions

Ques: is this DFA??

    b           a
    ↷     a    ↷
 --> (q0) -----> (q1)
        <------
           b




Finite Set of States : {q0, q1} ✅
Input Alphabets : {a, b} ✅
Initial state : q0 ✅
set of final states : {} ✅
Transition Function ✅


- Yes This is DFA

Ques: Is this DFA ??

     a,b         b
     ↷           ↷
--->(q0)<------((q1))
           a


Finite Set of States : {q0, q1} ✅
Input Alphabets : {a, b} ✅
Initial state : q0 ✅
set of final states : {q1} ✅
Transition Function ✅
- Yes

Ques: Languages Generated by the DFA

        a,b
-->((q0)) -------> (q1) ⤸ a,b


- Language Generated -> ϵ
- for 'a....' `b....` it reach to Dead State `q1`

Language -> Any set of strings over the alphabet ∑ = {a,b} ex:

  • L1 = {ab, ba, abab}
  • L2 = {a, ab, aba, …}
  • L3 = { } -> This represents the empty set, meaning it contains no strings at all
  • L4 = {ϵ} -> This language contains one string, which is the empty string ϵ.
  • L5 = {a}
  • L6 = {ϵ, a, b, aa, ab, ba, …}

Language Find Questions

Ques: Identify Language accepted by following DFA

           b
--->((1))--------------> (2)
   | ˄ <-------------- | ˄
   a | |        b        | | a
   | | a      b      a | |
   ˅ | --------------> ˅ |
  (3) <--------------- (4)
            b


- # a's even #b's even ✅
- # a's odd #b's even
- # a's even #b's odd
- # a's odd #b's odd


Solution :
Minimum Language Gnerated -> ϵ
Because Initial State is Final, and We Can Terminate Without any transition.


Its mean #a =0, #b=0 -> both even

Ques: Identify Language accepted by following DFA

           b
--->(1) ---------------> (2)
   | ˄ <-------------- | ˄
   a | |        b        | | a
   | | a      b      a | |
   ˅ | --------------> ˅ |
  ((3))<--------------- (4)
            b


- # a's even #b's even
- # a's odd #b's even ✅
- # a's even #b's odd
- # a's odd #b's odd


Solution :
Minimum Language Gnerated -> 'a'
Its mean #a =1 (odd), #b=0 (even)

Ques: Identify language accepted by following DFA

     0    0    0    0
--->()-->()-->()-->()-->()  ⬊
  1|   1|   1|   1|   1|     ⬊ 0
   ↓ 0  ↓ 0  ↓ 0  ↓ 0  ↓  0    ⬊
  ()-->()-->()-->()-->() ---> () ⤸ 0,1
  1|   1|   1|   1|   1|      ⬈
   ↓ 0  ↓ 0  ↓  0 ↓ 0  ↓    ⬈ 0
  ()-->()-->()-->()-->(())⬈
  ⤻    ⤻   ⤻    ⤻    ⤻
  1    1    1    1     1


- Length of the string atleast 6
- # 0's atleast 4 and # 1's exactly 2
- # 0's exactly 4 and 1's atleast 3
- None ✅


Solution:


Minimum Language Generated = {
000011, 010001, 011000...} #1 = 2, #0 = 4
}

DFA States Find for given Language Questions

Ques : How many states in minimal DFA for given Language L = { a^n.b^m | n>m & n,m>=1} ⭐ Ans:n & m Dependency Exist -> DFA Not Possible ❌

Ques: How many states in Minimal DFA for given Language L={a^(2^n) | n>=1 ⭐ Ans: a^2, a^4, a^8, a^16.... No common Difference between Terms -> Not Regular Language -> DFA Not Possible ❌

Ques: How many states in Minimal DFA for given Language L={a^n.b^m | n,m>=1 ⭐

L = {ϵ, a, aa, aaa..., b, bb, bbb..., ab, abb, aabbb...}


      a         b           a,b
      ↷    b   ↷      a    ↷
  --> ((q0))--->((q1))------>(q2) D.S


- 3 states ✅

Ques: How many states in Minimal DFA for given Language L={a^n.b^m | n>=1,m>=0 ⭐

L = {a, aa, aaa..., ab, abb, aabbb...}


    a        a          b
    ↷  a    ↷     b    ↷
--->(q0)--->((q1))----->((q2))
   |                      |
   └------->(q3)<---------┘
       b     ⤻     a
             a,b


- 4 states ✅

Length of String |w| -> Min no. of DFA States ⭐

  1. Length of the string exactly 4 -> n+2 (6) states

  2. Length of the string at least 5 -> n+1 (6) states

  3. Length of the string at most 4 -> n+2 (6) states

  4. Length of the string divisible by 4 -> n (4) states

**No. of # Alphabets # Odd/Even-> Min no. of DFA States ** ⭐

  1. a’s even (Divisible by 2)-> 2 states

    Section titled “a’s even (Divisible by 2)-> 2 states”

  2. a’s even (Not Divisible by 2) -> 2 states

    Section titled “a’s even (Not Divisible by 2) -> 2 states”

  3. a’s even and # b’s odd -> 2*2=4 States

    Section titled “a’s even and # b’s odd -> 2*2=4 States”

  4. a’s divisible by 3 and # b’s even -> 3*2=6

    Section titled “a’s divisible by 3 and # b’s even -> 3*2=6”

Questions on Minimization of DFA

Ques: How many states present in minimal DFA for given DFA

              (q3)
   b      b    /  \   b
   ↷      ↷  ⬋  a ⬊ ↷
--->(q0)-->((q1))--->((q2))
       a       <---
                 a


1. Eliminate any state which is not reachable i.e. elminate (q3)
2. Find Equivalent States, Algorithm :
  - Take All final states in one group and nonfinals in one group.
  - Non-final:{q0} Final:{q1, q2}
  - Make Transition Table
    q | a  | b
  ----|----|---
   q0 | q1 | q2
   q1 | q2 | q1
   q2 | q1 | q2
  - Transition on states fall into same group?
  - q1 ->(a,b) -> {q1, q2} yes
  - q2 ->(a,b) -> {q1, q2} yes
  - if yes then q1 = q2 (Equivalent State)


3. Draw Minimal DFA


   b      a,b
   ↷      ↷
-->(q0)-->((q1))
     a


- 2 states ✅

1.2 NFA

DFA is defined as
DFA = (Q, ∑, q₀, F, ∂ )
- All Same
- ∂ : Transition Function Q*∑ -> 2ꟴ

NFA to DFA Questions

Ques: Is this DFA? If No, then how many states present in minimal state DFA for given NFA

   a,b
   ↷           b
 -->(q0)--->(q1)--->((q2))
     a


DFA -> exactly 1 transition for each symbol


(q0,a)->q0, (q0,a)->q0 Not DFA ❌
Also (q1,a) -> No transition -> Not DFA❌


NFA ✅
Converting DFA to NFA - Draw Transition table


NFA :
   | a       | b  |
---|---------|----|
q0 | {q0,q1} | q0 |
q1 |    -    | q2 |
q2 |    -    |    |


- For empty transition, Change to Dead State
- For multiple transition, change to new state i.e. combination of q0 & q1 => [q0q1]
- If new state added, give its transition first to next entry, before remaining...




DFA :
       | a       | b  |
-------|---------|--------|
  q0   | [q0q1]  |   q0   |
[q0q1] | [q0q1]  | [q0q2] |
[q0q2] | [q0q1]  |   q0   |


Min DFA - 3 States ✅

NFA to DFA Conversion

  • n State in NFA -> Max 2^n States in DFA
  • n State in NFA -> Min 1 State in DFA

Ques: How many states in minimal DFA for following ϵ-NFA

  a,b                a,b
   ↷   ϵ       a     ↷
--> (q0)--->(q1)---->((q2))
      ⬆      |  ⬊ ϵ    ⬈ ϵ
    └------┘    ⬊  ⬈
      a          (q3)


               a,b
    ϵ      ϵ       ϵ   ↷
-->(q0)-->(q1)-->(q3)-->((q2))


=> Complete Language


 a,b
  ↷
((q0))


Min DFA - 1 State ✅

Ques: Convert ϵ-NFA to NFA ⭐

    0     (C)      1
    ↷    0↑ ↓1     ↷
-->(A)--->(B)--->((D))
       ϵ      ϵ


Without 'ϵ' NFA?
- No. of State will remain same
- Initial state will be same
- All states from which we can reach to Final state using only ϵ -> Make them final state


           (C)
1. (A)  (B)   (D)        Same #states


              (C)
2. -->(A) (B)   (D)      same initial state (A)


                  (C)
3. -->((A))  ((B))  ((D)) Final state {A,B,D}




4. A's Transitions
   ∂(A,0) = A
   ∂(A,0) = A + ∂(A,ϵ) = B
   ∂(A,0) = B + ∂(B,0) = C
   ∂(A,0) = B + ∂(B,ϵ) = D
   ∂(A,1) = D + ∂(D,1) = D


    0   0 (C)
    ↷   ⬈
-->((A))---->((B))   ((D))
    |    0             ⬆
    └─-----------------┘
             0,1


   B's Transition
   ∂(B,0) = C
   ∂(B,1) = D


   C's Transition
   ∂(C,0) = -
   ∂(C,1) = {B,D}




    0   0   (C)    1   1
    ↷   ⬈  0↑ ↓1  ⬊   ↷
-->((A))---->((B))--->((D))
    |    0          1  ⬆
    └─-----------------┘
             0,1

1.3 Regular Expression & Regular Expression

Regular Expression

  • The Simplest way of representing a regular language is known as Regular expression.
  • For every regular language regular expression can be constructed.
  • To construct regular expression following 3 operators are used.
  • + is known as union operator
  • . is known as concatenation operator
  • * is known as Kleene closure operator
  • DFA can Accept Every Regular Language
  • ~ For Every Regular Language DFA can be made

Ques: Regular Expression for the language `L={a^n.b^n | n>=0}

DFA Not Possible ❌ -> Regular Expression not Possible ❌

Ques: Construct Regular Expression that generates set of all even length palindrome string over {a,b} Ans: Palindrome Language with More than 1 Symbol -> Regular Expression Not Possible ❌

Ques: Construct regular expression that generates set of all strings of a’s and b’s where 4th input symbol is b from end ⭐ Ans: symbol at n from right side -> 2^n states

(a+b)* b (a+b)(a+b)(a+b)
  5    4   3    2    1


2^4 = 16 States ✅

Ques: Construct regular expression that generates set of all strings of a’s and b’s where 4th input symbol is a from left side ⭐ Ans: symbol at n from left side -> n+2 states

(a+b)(a+b)(a+b) a (a+b)*
  5    4   3    2    1


4+2 = 6 States ✅

Kleene’s Closure:

  • (a+b)* = (a+b*)* = (a* + b*)* = (a* + b)* = (a*b*)* complete language
  • a* + a* = a* = a*a*
  • a+b = b+a
  • a.b != ba

Final Automata to Regular Expressions Questions

Ques: Find Regular Expression for given F.A ⭐

--->((q0))---a-->(q1)
    | ↑ <--b---- |
  b | | a        | a
    ↓ |          ↓
   (q2) ----a---> (q3)


Remove Dead State (q3)


--->((q0))---a-->(q1)
    | ↑ <--b----
  b | | a
    ↓ |
   (q2)


Simplify


     ab
     ↷
-->((q0))
     ⤻
     ba


Language Accepted (ab + ba)* ⭐

Ques: Find Regular expression for given F.A?

      a          a
      ↷    b     ↷
 -->((q0))----->(q1)
      b⬉      ⬋ b
          (q2)
           a⤻


R.L = (a*.b.a*.b.a*.b)*
    => (a + b.a*.b.a*.b)*

Ques: Which of the following Regular Expression is equal to the given F.A

    b       b           b
    ↷       ↷      a   ↷
-->(q0)--->((q1))---->((q2))
                <--a---


- (a+b)*
- b*a*
- b*a(a+b)* ✅ -> b* a(b*, a, ab*, b*a.b*.a...)*
- b*a*(a+b)*


Solution by Elimination of options:
Minimum Language Supported by F.A -> 'a'
Minimum Language supported by :
(a+b)* -> ϵ ❌
(b*a*) -> ϵ ❌
b*a(a+b)* -> `a` Could be answer
b*a*(a+b)* -> ϵ ❌

No. of States in minimal DFA

  • a*.b* -> n+1 = 2+1 = 3
  • a*.b*.c*.d* -> 4+1 = 5
  • 0*.1*.2*.....9* -> 10+1 = 11
  • (a+b)* abab -> ending with n length = n+1 = 4+1 = 5
  • (a+b)* ababa (a+b)* -> n length substring = n+1 = 5 + 1 = 6

Ques: Is the Language L1 = {a^n.b^n.c^n | n<=1000} Regular? Ans: Yes Because it is finite and have no dependency (And difference between terms in finite doesn’t matter)

Language:
╭------------╮
| Regular    |
| ╭--------╮ |
| | Finite | |
| ╰--------╯ |
╰------------╯


If regular -> need not be finite
If finite -> it will be regular also

Ques: Which of the following is Regular?

- L = {a^(n^n) | n>=1}
- L = {a^p | p is prime no. }
- L = {a^(2^n) | n>=1 }
- None ✅


In all other options, R.E is infinite and no common difference between terms.
  • Reverse String -> w^R is reverse of w w = abacd -> w^R = dcaba
  • Palindrome -> w.x.w^r

Ques: Which of the following is Regular?

- L = {W.W^R | Wϵ(a+b)*}
- L = {W.C.W^R | Wϵ(a+b)*}
- L = {W.b.W^R | Wϵ(a)*}
- None ✅


In all other options, R.E is infinite and and reverse dependency on each other.

Ques: Which of the following is Regular? ⭐

- L = {W.W^R.X | W,Xϵ(a+b)*} ✅
- L = {X.W.W^R | W,Xϵ(a+b)*} ✅
- L = {W.X.W^R | W,Xϵ(a+b)*} ✅
- None


In all these options, R.E is same as (a+b)* i.e. complete language and so R.L


My doubt. But this also contain infinite and dependancy 🤔❓❓

Closure Properties of Regular Expression

  • Subset Operation
  • Infinite Union Operation
  • Infinite Intersection Operation

Question from closure property

Ques: Which of the following is true?

1. Subset of Regular set is always Regular
2. Subset of any Infinite set is always Regular
3. Subset of any Non-Regular set is always Regular
4. None ✅


❓❓❓ change subset of to symbol
1. {a^n.b^n} subset of  (a+b)* is not regular
2. {a^n.b^n} subset of {a^n.b^n.c^m | n,m>=0} is not regular
3. {a^n.b^n} subset of {a^n.b^n.c^m} is not regular

NAT Type of Questions

❓❓❓ Change Intersection symbol L1^L2

Ques: How many states present in minimal state DFA for L1 ^ L2 where L1=(a+b)*a L2=(a+b)*b Ans: Only 1 State

Intersection = {} empty set


   a,b
    ↷
-->()

2. Grammar

Section titled “2. Grammar”

Terminal -> a, b, c, 1, 0 Non-Terminal -> T, S, A, B

  • Set of rules used to describe strings of a language known as Grammar
  • Formal definition of grammar is

G = (N, T, P, S)

  • N : Non Terminals of variables
  • T : Terminals
  • P : No. of productions
  • S : Starting symbol

❓❓ Change alpha beta to symbol

  • For every language grammar exit & every grammar generates one language.
  • All grammars is of a from alpha replacement of alpha->Beta, where Beta is replacement of alpha

Derivation:

  • The process of deriving strings from the given grammar known as derivation.
  • The derivation can be either left most derivation or right most derivation
  • Left Most Derivation -> Left most non-terminal is replaced by its R.H.S part at every step
  • Right Most Derivation -> Right most non-terminal is replaced by its R.H.S part at every step

Derivation Tree / Parse Tree

  • Tree representation of the derivation is known as parse tree
  • All leaf of the parse tree is known as yield of parse tree.
  • While reading yield from left to right sentence of the grammar can be generate
    S
    /   \
   A     B                S -> AB
   |     |                A -> a
   a     b                B -> b

Identify Language generated by grammar

Ques: Identify Language generated by grammar S->aSa | bSb | ϵ Ans: The Regular Language is {W.W^R | Wϵ (a+b)*}

S         S
|       / | \
ϵ      a  S  a
        / | \
       b  S  b
          |
          ϵ


Even Length Palindrome

Ques: Construct Grammar for the following languages. S->aAa | bAb | a | b , A->aA | bA | ϵ Ans: Starting and ending with same symbol

A -> aA | bA | ϵ     => (a+b)*


S -> {a.(a+b)*.a + b.(a+b)*.b + a + b}

2. 2 Context Free Grammar

Ques: Which of the following is Regular Grammar?

- S -> aSa | bSb | ϵ
- S -> aSb | ab
- S -> AB, A->a , B->b
None ✅


❓❓ Change symbol of alpha and belong to




All options 1, 2, 3 are CFG not RG


Don't Identify Grammar, using Language Rule.
CFG can generate both Regular and non-regular language ⭐


Context Free Grammar : Left Side One Non-Terminal, Right Side any no. of Non Terminal
A -> alpha
albha belong to (V+T)*


Regular Grammar :Left Side One Non-Terminal,  Right side atmost 1 non-terminal
A -> xB | x : Right linear Grammar
A -> Bx | x : Left Linear Grammar

Ambiguous Grammar -> For at least one string more than one Parse tree exist.

  • Verification of Ambiguity is undecidable problem i.e. no algorithm exist

Ambiguous Ex:

S -> AA
A -> aA | a


          aaa
         ⬋   ⬊
    S             S
   / \           /  \
  A  A           A   A
  |   |          |  / \
  a   A          a  a  A
      |                |
      a                a

Ques: Which of the following is Unambiguous Grammar

- S -> SS|ϵ
- S -> aSbS|bSaS|ϵ
- S -> AaAb | BbBa, A->ϵ , B->ϵ ✅
- None

Normal Form of CFG

  1. Chomsky Normal Form
  2. Greibach Normal Form

3. Push Down Automata

Section titled “3. Push Down Automata”

3.1 Context Free Language

4. Turing Machine

Section titled “4. Turing Machine”

5. Undecidability

Section titled “5. Undecidability”