Minimal Deterministic Finite Automata

Let the i/p alphabet = {0,1} for the following questions :

$\color{red}{Q) \mathbf{About\; String \;Lengths : }}$

$\color{green}{i) \text{ Length of the strings exactly = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Length of the strings atmost = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{iii) \text{ Length of the strings atleast = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{iv) \text{ Length of the strings divisible by n  :  }}\color{blue}{\text{  n}}$

$\color{green}{v) \text{ Length of the strings atleast = m & atmost = n  :  }}\color{blue}{\text{  n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

 

$\color{red}{Q) \mathbf{About\; Prefix\; Lengths : }}$

$\color{green}{i) \text{ Length of the prefix  = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Length of the prefix  = m & total length of the string exactly = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the prefix  = m & total length of the string atmost = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the prefix  = m & total length of the string atleast = n :  }}\color{blue}{\text{  max(m,n)+2}}$

$\color{green}{v) \text{ Length of the prefix  = m & total length of the string divisible by n :  }}\color{blue}{\text{ m+n+1}}$

 

$\color{red}{Q) \mathbf{About\; Suffix\; Lengths : }}$

$\color{green}{i) \text{ Length of the suffix  = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{ii) \text{ Length of the suffix  = m & total length of the string exactly = n :  }}\color{blue}{\text{ n+2}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the suffix  = m & total length of the string atmost = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the suffix  = m & total length of the string atleast = n :  }}\color{blue}{\text{  max(m,n)+1}}$

$\color{green}{v) \text{ Length of the suffix  = m & total length of the string divisible by n :  }}\color{blue}{\text{ m+n}}$

 

$\color{red}{Q) \mathbf{About\; Substring\; Lengths : }}$

$\color{green}{i) \text{ Length of the substring  = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{ii) \text{ Length of the substring  = m & total length of the string exactly = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iii) \text{ Length of the substring  = m & total length of the string atmost = n :  }}\color{blue}{\text{ (n-m+1)*(m+1)+1}}\color{magenta}{\text{ [ note:- n ≥ m ]}}$

$\color{green}{iv) \text{ Length of the substring  = m & total length of the string atleast = n :  }}\color{blue}{\text{  (n-m+1)*(m+1)}}$

$\color{green}{v) \text{ Length of the substring  = m & total length of the string divisible by n :  }}\color{blue}{\text{ (n)*(m+1)}}$

 

$\color{red}{Q) \mathbf{About\; Fixed\; position : }}$

$\color{green}{i) \;\;n^{th}\text{ position from the left side of the string is fixed to ‘0’  : }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \;\;n^{th}\text{ position from the right side of the string is fixed to ‘0’  : }}\color{blue}{\text{ }2^{n}}$

 

$\color{red}{Q) \mathbf{About\; Number \;of\;occurances : }}$

$\color{green}{i) \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Number of ZERO’s in the strings atmost = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{iii) \text{ Number of ZERO’s in the strings atleast = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{iv) \text{ Number of ZERO’s in the strings divisible by n  :  }}\color{blue}{\text{  n}}$

 

let two positive integers m and n, neither m divides n nor n divides m:

$\color{green}{v) \text{ Number of ZERO’s in the strings divisible by n and m  :  }}\color{blue}{\text{ LCM(n,m) }}$

$\color{green}{vi) \text{ Number of ZERO’s in the strings divisible by n or m  :  }}\color{blue}{\text{ LCM(n,m) }}$

$\color{green}{vii) \text{ Number of ZERO’s in the strings divisible by n but not by m  :  }}\color{blue}{\text{ LCM(n,m) }}$

 

let two positive integers m and n, either m divides n or n divides m:

$\color{green}{viii) \text{ Number of ZERO’s in the strings divisible by n and m  :  }}\color{blue}{\text{ MAX(n,m) }}$

$\color{green}{ix) \text{ Number of ZERO’s in the strings divisible by n or m  :  }}\color{blue}{\text{ MIN(n,m) }}$

$\color{green}{v) \text{ Number of ZERO’s in the strings divisible by n but not by m  :  }}\color{blue}{\text{ MAX(n,m) }}$

 

$\color{red}{Q) \mathbf{About\; independent Data items : }}$

While multiplying, you should take care of productive states.

$\color{green}{i) \text{ no.of ZERO’s are exactly ‘n’ and no.of ONE’s exactly ‘m’  : }}$

$\;\;\;\color{blue}{ \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}} = \color{magenta}{\text{  (n+1)+(1 DS)}}$

$\;\;\;\color{blue}{ \text{ Number of ONE’s the strings exactly = m  :  }}\color{blue}{\text{  m+2}} = \color{magenta}{\text{  (m+1)+(1 DS)}}$

$\color{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$

 

$\color{green}{ii) \text{ no.of ZERO’s are exactly ‘n’ and no.of ONE’s atleast ‘m’  : }}$

$\;\;\;\color{blue}{ \text{ Number of ZERO’s the strings exactly = n  :  }}\color{blue}{\text{  n+2}} = \color{magenta}{\text{  (n+1)+(1 DS)}}$

$\;\;\;\color{blue}{ \text{ Number of ONE’s the strings exactly = m  :  }}\color{blue}{\text{  m+2}} = \color{magenta}{\text{  (m+1)}}$

$\color{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$

 

Supported Documents : https://drive.google.com/open?id=1haPRlS78p7RA7ugMhaK9Li6370ZjaEcx

posted in Theory of Computation Nov 7, 2019 edited Feb 5 by
2,667 views
28
Like
12
Love
0
Haha
0
Wow
0
Angry
0
Sad

13 Comments

13 Comments

Like
1
Great effort!!

Thank you so much
Like
Wow! Thank you so much!
Like
Thanks Sir
Like
1

@Arjun

Sir can we have an option to save such blogs as an important marker in the form of list for revising them later on.

Like
Blog favorite button doesnt work?
Like
Favourite option does work.

But list options have more custom options like important, see later etc. Which are very good to segregate the content according to need.

So, this would be of so much use.
Like
Favorite is not working for blogs..

In favorites it only shows favorite marked questions, not blogs
Like

Hi @, For L = {xaay| x,yE(a+b)+}

Here the sub string length = 2 and string length is at least 4 so when I am using the formula (n-m+1)*(m+1) I am getting (4-2+1)*(2+1) = 3*3 = 9 but the actual answer will be 5 and here is the dfd.

 

Like
1
L$_1$ = { x a a y | x,y ∈ (a+b)$^+$}, L$_2$ = {strings such that Substring of length 'm' and total length is atleast 'n' }

are different.

L$_2$ have a string "a a bb" which is not belongs to L$_1$.
edited Oct 4 by
Like
thanks sir
Like
Thank You So Much...
Like
Firstly, thank you very much Sir, from where do you collect such authentic resources?

or did you prove these yourselves?

I have gone through reference book (Peter Linz), nptel and foreign pdfs too. I didn't find these.
Like
1
proved.

Subscribe to GO Classes for GATE CSE 2022