Recent posts in Theory of Computation

Recent posts in Theory of Computation

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

Deepakk Poonia (Dee) posted in Theory of Computation Aug 30, 2020
11,855 views
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 =...

Shaik Masthan posted in Theory of Computation Nov 7, 2019 edited Feb 5 by Shaik Masthan
2,285 views
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.$...

Arjun posted in Theory of Computation Sep 20, 2019
by Arjun
3,336 views
4

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

Part 2 is added now...

Decidability Slides Updated

Arjun posted in Theory of Computation Jan 16, 2019 edited Jan 27, 2019 by Arjun
by Arjun
3,855 views
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}
What do you know about...
Manoja Rajalakshmi A posted in Theory of Computation Oct 6, 2018
1,161 views
6

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

Balaji Jegan posted in Theory of Computation Sep 14, 2018 edited Nov 23, 2018 by Balaji Jegan
2,265 views
To see more, click for the full list of questions or popular tags.
Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true