Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

5 votes
2 answers
3903
Halting Problem of Turing Machines
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
User Avatar
0 votes
1 answer
3905
Finite Automata
Construct dfa for set of all strings where every pair of consecutive 0's occurs before any pair of adjacent 1's ?
Construct dfa for set of all strings where every pair of consecutive 0's occurs before any pair of adjacent 1's ?
User Avatar
0 votes
1 answer
3908
Turing Machine
Construct the Turing Machine that accepts the language of palindromes over {a, b}. Also specify the moves trace the strings abaa, abba, aabaa.
Construct the Turing Machine that accepts the language of palindromes over {a, b}. Also specify the moves trace the strings abaa, abba, aabaa.
User Avatar
5 votes
6 answers
3909
Minimized DFA no of states || Peter Linz
$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$ Minimal DFA for the above language ?
$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$Minimal DFA for the above language ?
User Avatar
1 votes
1 answer
3910
Automata
What is R-L, where R is a regular language and L is context free. Options are a.Regular, b.Context free,c.Context Sensitive ,d.None of this
What is R-L, where R is a regular language and L is context free.Options are a.Regular, b.Context free,c.Context Sensitive ,d.None of this
User Avatar
1 votes
1 answer
3912
How many final states ?
How many final states required in the equivalent DFA ?
How many final states required in the equivalent DFA ?
User Avatar
1 votes
1 answer
3913
Toc Ullman
Give DFA of The set of all strings which when interpreted as a binary integer is a multiple of 3.
Give DFA of The set of all strings which when interpreted as a binary integer is a multiple of 3.
User Avatar
2 votes
1 answer
3914
TOC- regular languages
Let the homomorphism defined over alphabet Σ{0, 1} is h(0) = aa and h(1) = aba, and L = (ab + ba)*a then what is h-1(L)?
Let the homomorphism defined over alphabet Σ{0, 1} is h(0) = aa and h(1) = aba, and L = (ab + ba)*athen what is h-1(L)?
User Avatar
1 votes
1 answer
3915
Theory of computation
Set of all strings over {0,1} containing at most one pair of consecutive 1's. Give regular expression and equivalent minimized DFA.
Set of all strings over {0,1} containing at most one pair of consecutive 1's.Give regular expression and equivalent minimized DFA.
User Avatar
1 votes
1 answer
3916
toc - doubt
W(Wr)+, w belongs to (0*,1*) is Csl because? Is it because we cant decide the no of Wr or the content inside the Wr or both? so if 0111,011,001 a seperate kind of comparison for each? <------- this is the reason?
W(Wr)+, w belongs to (0*,1*) is Csl because? Is it because we cant decide the no of Wr or the content inside the Wr or both? so if 0111,011,001 a seperate kind of compari...
User Avatar
1 votes
1 answer
3921
Toc
In pumping lemma for CFL a^nb^n ....the pumping is done on equal number of a and b then pumping lemma is valid for this CFL...but when I take unequal a and b pumping lemma is invalid for this CFL...am I doing wrong any where ?
In pumping lemma for CFL a^nb^n ....the pumping is done on equal number of a and b then pumping lemma is valid for this CFL...but when I take unequal a and b pumping lemm...
User Avatar
1 votes
2 answers
3923
Mininmal DFA
What will a minimal DFA over alphabet {a,b} which accepts all strings in which second symbol from RHS is always 'a' look like?
What will a minimal DFA over alphabet {a,b} which accepts all strings in which second symbol from RHS is always 'a' look like?
User Avatar
3 votes
1 answer
3924
Video Lectures by Shai Simonson
Are the Video Lectures by Shai Simonson self sufficient for GATE or do they miss out on certain parts ?
Are the Video Lectures by Shai Simonson self sufficient for GATE or do they miss out on certain parts ?
User Avatar
2 votes
1 answer
3925
self doubt
Convert into regular expression using state elimination method.
Convert into regular expression using state elimination method.
User Avatar
3 votes
3 answers
3926
gate ,toc
a*b*b (a+ (ab)*)* b* shortest string generated by this RE?
a*b*b (a+ (ab)*)* b*shortest string generated by this RE?
User Avatar
3 votes
2 answers
3927
DFA
What is the language accepted by the following DFA ... ending with zero set of all strings starting and ending with zero 2nd option is true but what abut the 3rd option it is also Correct I Guess
What is the language accepted by the following DFA $\Sigma=(0,1)?Set of strings starting with 0 and have odd number of switchings (from 0 to 1 or 1 to 0, for example, 101...
User Avatar
Page: