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, 2021 by
5,784 views
44
Like
17
Love
0
Haha
0
Wow
0
Angry
0
Sad

19 Comments

19 Comments

Like
1
Great effort!!

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

@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
1
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, 2021 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
3
proved.
Like
1
Thank you sir for this wonderful observation.
Like
What is the difference between (v, vi, vii )and (vii, ix, v)

Both of them have the same statement but different answers
Like

@faisal_sayyed

I didn't get you. Can you elaborate more ?

Like
1
In first case (m,n) be (3,5) or (7,11) or (6,9). These can't be the valid pairs for second case.
Like
1

Ooh sorry, my bad.

I read both neither and either as neither. 

Got it. Thank you!