Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

1 votes
2 answers
2403
Regular Expressions
$L_1=\{a^nb^m\mid n\geq 3,m\leq 4\}$ Find complement of $L_1.$
$L_1=\{a^nb^m\mid n\geq 3,m\leq 4\}$Find complement of $L_1.$
User Avatar
27 votes
6 answers
2407
GATE CSE 2018 | Question: 7
The set of all recursively enumerable languages is: closed under complementation closed under intersection a subset of the set of all recursive languages an uncountable set
The set of all recursively enumerable languages is:closed under complementationclosed under intersectiona subset of the set of all recursive languagesan uncountable set
User Avatar
24 votes
2 answers
2408
GATE CSE 2018 | Question: 6
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true? $k \geq 2^n$ $k \geq n$ $k \leq n^2$ $k \leq 2^n$
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?$k \geq 2^n...
User Avatar
2 votes
1 answer
2409
Complement of CFL
How to prove that $\text{"complement of L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}" $?
How to prove that $\text{"complement of L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}" $?
User Avatar
0 votes
1 answer
2410
Doubt
What is encoding in Finite State machine?
What is encoding in Finite State machine?
User Avatar
7 votes
3 answers
2413
CMI2017-A-01
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$ $(a^*b+b)^*$ $(a+b^*)^*$ $(a^*b)^*$
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$$(a^*b+b)^*$ $(a+b^*)^*$$(a^*b)^*$
User Avatar
0 votes
1 answer
2414
MadeEasy Test Series: Theory Of Computation - Turing Machine
Consider the Turing machine when the input is still left and the turing machine halts will it accept it by halting or will it process the entire input left??
Consider the Turing machine when the input is still left and the turing machine halts will it accept it by halting or will it process the entire input left??
User Avatar
0 votes
1 answer
2416
Grammer
Can I give any grammer for the language L = { anbncn / n>=1} Like this----
Can I give any grammer for the language L = { anbncn / n>=1} Like this
User Avatar
0 votes
1 answer
2417
Regular expression
S -> AaB A -> aC | $\epsilon$ B -> aB | bB | $\epsilon$ C -> aCb | $\epsilon$ Is the regular expression for the above is this: a(a + b)* a ( a* + b* )* ?
S - AaBA - aC | $\epsilon$B - aB | bB | $\epsilon$C - aCb | $\epsilon$Is the regular expression for the above is this:a(a + b)* a ( a* + b* )* ?
User Avatar
0 votes
0 answers
2418
TOC ACE
User Avatar
0 votes
4 answers
2419
Regular Expression
Can I write $a^* + b^* = (a + b)^*$ ????
Can I write $a^* + b^* = (a + b)^*$ ????
User Avatar
0 votes
0 answers
2420
Test Series
We need to draw DFA for it. and then NFA.? Please tell the approach?
We need to draw DFA for it. and then NFA.?Please tell the approach?
User Avatar
0 votes
0 answers
2421
Type of Language
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
User Avatar
0 votes
1 answer
2422
Minimal DFA
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____ My ans : 4 states given ans : 5 states
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____My ans : 4 states given ans : 5 states
User Avatar
2 votes
0 answers
2423
#Practise Class of Languages
$xwxw^r |\ w,x \in (a,b)^*$ $wxw^{r}x |\ w,x \in (a,b)^*$
$xwxw^r |\ w,x \in (a,b)^*$$wxw^{r}x |\ w,x \in (a,b)^*$
User Avatar
1 votes
2 answers
2424
Turing Machine - Membership Problem
Is membership problem for TM decidable or undecidable?
Is membership problem for TM decidable or undecidable?
User Avatar
4 votes
1 answer
2425
Theory of computation
The minimal finite automata accepting the set of all strings over 0,1 starting with 1 that interpreted as a binary representation of an integer are congruent to 0 modulo 5 has ___ states. What is this language?
The minimal finite automata accepting the set of all strings over 0,1 starting with 1 that interpreted as a binary representation of an integer are congruent to 0 modulo ...
User Avatar
0 votes
1 answer
2426
Regular Languages
Language {w | ww=www} is regular. How and what is this language?
Language {w | ww=www} is regular.How and what is this language?
User Avatar
0 votes
0 answers
2427
#TOC Doubt
L = anbm / n,m>=1 What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same values!?
L = anbm / n,m>=1What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same valu...
User Avatar
0 votes
1 answer
2429
Turing Machine
...................................
...................................
User Avatar
Page: