search
Log In

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 Nov 7, 2019 in Theory of Computation 1,297 views
20
Like
8
Love
0
Haha
0
Wow
0
Angry
0
Sad

10 Comments

Great effort!!

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

@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.

Blog favorite button doesnt work?
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.
Favorite is not working for blogs..

In favorites it only shows favorite marked questions, not blogs

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.

 

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$.
can anyone tell how to use the information given in this blog its seems very imp ,it might help me in solving questions faster .
...