First let me define what is “Divisibility language”.

We have two very similar looking type of languages. I call one type “Length divisibility language” and other I call “Divisibility language”

"Length divisibility machines/languages" are different from "divisibility languages".

Let me define what I mean by “Length divisibility language” and by “Divisibility language” :

**Length divisibility language :** Given binary string w, we ask questions like :

(length of w) mod n = r, Or

(#0 in w) mod n = r, Or

(#1 in w) mod n,

etc.

**Divisibility language...**

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

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$

We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the final state for divisibility by $3$. If we add a '0' transition from this state to another state and make it FINAL, we get divisibility by $6$ as a '0' at end ensure number is divisible by $2$ and also retains the property that the number is divisible by $3$ which makes it divisible by $6.$ Add one more state like this and we get numbers divisible by $3\times 2\times 2 = 12.$...

**Regular Language**- alphabets, language(set of strings), language class or language family

All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable recursive set of languages outside recursively enumerable languages

**Finite Automata**- Deterministic Automata and Non Deterministic Automata- mathematical representation

**Number of DFA's possible**

**with two states over {0,1}**

What do you know about...

PLEASE CHECK MY UNDERSTANDING:-

**1. Halting Problem:-**

**a) A turing machine halts after running for exactly k steps on any input**

This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

**b) A turing machine halts after running for atmost k steps on any input**

This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

**c) A turing machine halts after running for atleast k steps on any input**

This is SEMI-DECIDABLE, as we can construct a Turing...