Recent questions and answers in Theory of Computation

0 votes
0 answers
1
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countab...
Himanshu555 asked in Theory of Computation Aug 5
17 views
0 votes
2 answers
3
Can set of terminal be empty in a grammar? Is epsilon (null string) counted as a terminal symbol?
manikantsharma answered in Theory of Computation Jul 31
686 views
0 votes
1 answer
4
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
ankitgupta.1729 answered in Theory of Computation Jul 30
62 views
1 vote
0 answers
5
equivalence of two regular language can be tested in (worst case)? polynomial time sub linear time exponential time poly logarithmic time
jugnu1337 asked in Theory of Computation Jul 27
61 views
0 votes
1 answer
6
0 votes
1 answer
7
Where can I get the solution manual for An Introduction to Formal Languages and Automata by peter linz for the back exercises?
Bikram 1 answered in Theory of Computation Jul 21
169 views
0 votes
0 answers
8
0 votes
1 answer
9
0 votes
1 answer
10
If for every RE there exist a TM that accepts it, is it possible that for 2 different RE languages there exists a single TM that accepts them?
tanBit answered in Theory of Computation Jul 20
by tanBit
69 views
0 votes
1 answer
12
0 votes
0 answers
22
0 votes
2 answers
24
Example: 11110100000111 should be accepted. There are 6 zeros. 6 is divisble by 2 and 3. This machine required at least six states.
ritik456 answered in Theory of Computation Jul 11
75 views
1 vote
2 answers
27
0 votes
0 answers
31
How is equality problem for DCFL decidable?
sara02 asked in Theory of Computation May 24
by sara02
61 views
0 votes
0 answers
33
Examples of accepted words: 1011, 101101, 1111 Example of non-accepted words: 101, 1001, 010 The solution says the min-DFA contains 5 states but I could only do it in 4. ...
koushriek asked in Theory of Computation May 19
187 views
Help get things started by asking a question.