Recent posts in Theory of Computation

1

Divisibility language and Minimum Number of States in a DFA accepting a binary number divisible by 'n'

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 " ... -main.pdf https://cs.stackexchange.com/questions/85850/minimum-number-of-states-in-dfa-accepting-binary-number-with-decimal-equivalent

posted Aug 30, 2020 in Theory of Computation Deepakk Poonia (Dee) 11,563 views

2

Minimal Deterministic Finite Automata

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{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 Shaik Masthan
edited Feb 5 by Shaik Masthan 2,008 views

3

Minimum Number of States in a DFA accepting a binary number divisible by 'n'

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 ... by $\text{LCM}(m,n).$ To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$

posted Sep 20, 2019 in Theory of Computation Arjun 2,643 views

4

Decidability Slides

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

posted Jan 16, 2019 in Theory of Computation Arjun
edited Jan 27, 2019 by Arjun 3,676 views

5

Theory of Computation - GO Classroom

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 ... only- finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.

posted Oct 6, 2018 in Theory of Computation Manoja Rajalakshmi A 1,074 views

6

DECIDABILITY

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 ... DECIDABLE(same as above). c) A turing machine replaces the characters on the tape atmost n times on any input SEMI-DECIDABLE(same as above).

posted Sep 14, 2018 in Theory of Computation Balaji Jegan
edited Nov 23, 2018 by Balaji Jegan 2,143 views

7

Rice Theorem

Nice papers with examples: http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-reductions-rice.pdf http://people.cs.aau.dk/~srba/courses/CC-08/rice-uk.pdf

posted Jan 22, 2016 in Theory of Computation bahirNaik 346 views

8

Important Questions in Theory of Computation

Important Ones https://gateoverflow.in/questions/theory-of-computation?sort=featured More Questions http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/assign6/pb9.html Problem Set 1 Problem Set 2

posted Aug 9, 2015 in Theory of Computation Arjun 8,503 views

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

GO Book for GATECSE 2022

Subjects

Network Sites

Recent posts in Theory of Computation

Log In

Register

GO Book for GATECSE 2022

Recent Posts

Subjects

Recent Blog Comments

Network Sites

Recent posts in Theory of Computation