Filter
1

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

2

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 =... 3 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.\$...

4

These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear.

Decidability Slides Updated

5
Day Date Contents Slides Assignments  1  Sep 27 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}
6

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

7
8
To see more, click for the full list of questions or popular tags.