Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

18 votes
8 answers
4051
ISRO2016-38
What is the highest type number that can be assigned to the following grammar? $S\to Aa,A\to Ba,B \to abc$ Type 0 Type 1 Type 2 Type 3
What is the highest type number that can be assigned to the following grammar?$$S\to Aa,A\to Ba,B \to abc$$Type 0Type 1Type 2Type 3
User Avatar
8 votes
3 answers
4054
ISRO2014-79
Consider the following Deterministic Finite Automaton $M$. Let $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of strings in $S$ that are accepted by $M$ is 0 1 2 3
Consider the following Deterministic Finite Automaton $M$.Let $S$ denote the set of eight bit strings whose second, third, sixth and seventh bits are 1. The number of str...
User Avatar
6 votes
4 answers
4056
ISRO2014-12
How many states are there in a minimum state deterministic finite automaton accepting the language $L = \{w \mid w \in \{0,1\}^*,$ number of 0's is divisible by 2 and number of 1's is divisible by 5, respectively $\}$? 7 9 10 11
How many states are there in a minimum state deterministic finite automaton accepting the language $L = \{w \mid w \in \{0,1\}^*,$ number of 0's is divisible by 2 and num...
User Avatar
3 votes
3 answers
4058
Finite Automata
There are exactly ______different finite automata with 3 states x,y,and z over the alphabet {a,b} where x is always the start state 1)64 2) 256 3) 1024 4)5832
There are exactly ______different finite automata with 3 states x,y,and z over the alphabet {a,b} where x is always the start state1)64 2) 256 3) 1024 4)5832
User Avatar
1 votes
2 answers
4059
Cfl
If L1 is CfL and L2 is CfL then state true or false?? i)L1-L2 is CSL ii)L1 intersection L2 is CSL.. Iii)L1 - L2 is Recursive iv)L1(compliment) is CSL Give the reason
If L1 is CfL and L2 is CfL then state true or false??i)L1-L2 is CSLii)L1 intersection L2 is CSL..Iii)L1 - L2 is Recursiveiv)L1(compliment) is CSLGive the reason
User Avatar
2 votes
3 answers
4061
TOC John C Martin Finite Automata
Draw an FA accepting the language of all strings that begin or end with aa or bb, where indicated language is over {a, b} .
Draw an FA accepting the language of all strings that begin or end with aa or bb, where indicated language is over {a, b} .
User Avatar
2 votes
1 answer
4062
Theory Of Computation
To complement the language , we complement the machine by altering final/non-final states. My question is , should that machine necessarily be a DFA? Can't we apply the same concept to NFA?
To complement the language , we complement the machine by altering final/non-final states.My question is , should that machine necessarily be a DFA? Can't we apply the sa...
User Avatar
2 votes
1 answer
4063
The meaning of the regular expression
The meaning of the regular expression (a+b)(a+b) is A)Strings of a's and b's where length is 2 B)Strings of a's and b's of any length. C)Null string D)None
The meaning of the regular expression (a+b)(a+b) isA)Strings of a's and b's where length is 2B)Strings of a's and b's of any length.C)Null stringD)None
User Avatar
1 votes
3 answers
4064
NFA to DFA
NFA can be converted into DFA using Sub set construction method Lazy evaluation method either A or B both A and B
NFA can be converted into DFA usingSub set construction methodLazy evaluation methodeither A or Bboth A and B
User Avatar
2 votes
1 answer
4065
Regularity of the strings
Which of the following is/are not regular A)strings of 0's whose length is a perfect square B)set of all palindromes made up of 0's & 1's C)Strings of 0's whose length is prime number D)all the above
Which of the following is/are not regularA)strings of 0's whose length is a perfect squareB)set of all palindromes made up of 0's & 1'sC)Strings of 0's whose length is pr...
User Avatar
6 votes
4 answers
4067
ISRO2011-79
A problem whose language is recursion is called? Unified problem Boolean function Recursive problem Decidable
A problem whose language is recursion is called?Unified problemBoolean functionRecursive problemDecidable
User Avatar
2 votes
1 answer
4070
Finite Automation
A language L is accepted by finite automata if and only if it is Right linear Primitive Recursive Context Sensitive Recursive
A language L is accepted by finite automata if and only if it isRight linearPrimitive RecursiveContext SensitiveRecursive
User Avatar
0 votes
1 answer
4071
Pushdown automation
A language L is accepted by a pushdown automation if and only if it is A) Context Sensitive B)Recursive C)Context Free D)Right Linear
A language L is accepted by a pushdown automation if and only if it isA) Context SensitiveB)RecursiveC)Context FreeD)Right Linear
User Avatar
1 votes
2 answers
4072
ToC \ Reg Expression
Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c}
Give a regular expression for L = {set of all strings in which number of a's are multiples of 3}∑={a,b,c}
User Avatar
7 votes
4 answers
4073
ISRO2011-68
Which of the following sentences can be generated by S -> aS $\mid$ bA A -> d $\mid$ cA bccdd abbcca abcabc abcd
Which of the following sentences can be generated by S - aS $\mid$ bAA - d $\mid$ cAbccddabbccaabcabcabcd
User Avatar
0 votes
1 answer
4074
Equivalence of DPDA and TM
Which of the following statements are true? 1. Multitape TMs are equivalent to single tape TM 2. Non deterministic TMs are equivalent to deterministic PDA 3. Both 1 and 2 4. Neither 1 nor 2
Which of the following statements are true?1. Multitape TMs are equivalent to single tape TM2. Non deterministic TMs are equivalent to deterministic PDA3. Both 1 and 24. ...
User Avatar
0 votes
1 answer
4075
Which of the following can be recognized by a Turing machine?
Which of the following can be recognized by a Turing machine? 1. Palindrome recognition 2. GCD computation 3. SQUARE(SQUARE(.....(x)) where SQUARE(x) = x 2 4. All the above
Which of the following can be recognized by a Turing machine?1. Palindrome recognition2. GCD computation3. SQUARE(SQUARE(.....(x)) where SQUARE(x) = x 24. All the above
User Avatar
3 votes
1 answer
4076
TOC CFG
If language $L=\{a^n b^n \mid n \geq 0\}$, then language $L^2$ is given by $\{a^{2n} b^{2n} \mid n \geq 0\}$ $\{a^n b^n a^n b^n \mid n \geq 0\}$ $\{a^n b^n \mid n \geq 0\}$ $\{a^n b^n a^m b^m \mid n, m \geq 0\}$
If language $L=\{a^n b^n \mid n \geq 0\}$, then language $L^2$ is given by$\{a^{2n} b^{2n} \mid n \geq 0\}$$\{a^n b^n a^n b^n \mid n \geq 0\}$$\{a^n b^n \mid n \geq 0\}$$...
User Avatar
1 votes
2 answers
4077
Toc CFG
The production rules for a given context-free grammar are $S \rightarrow aA, A \rightarrow bB, A \rightarrow aB$ and $B \rightarrow a$ in Chomsky normal form Greibach normal form Simple form None of the above
The production rules for a given context-free grammar are $S \rightarrow aA, A \rightarrow bB, A \rightarrow aB$ and $B \rightarrow a$ inChomsky normal formGreibach norma...
User Avatar
1 votes
1 answer
4078
Is this language regular? L1:{wxwR∣w,x∈{a,b}∗ and |w|,|x|>0},wR is the reverse of string w
Is this language regular? L1:{wxwR∣w,x∈{a,b}∗ and |w|,|x|>0}, wR is the reverse of string w Please explain..
Is this language regular? L1:{wxwR∣w,x∈{a,b}∗ and |w|,|x|>0},wR is the reverse of string wPlease explain..
User Avatar
10 votes
2 answers
4079
ISRO2015-43
Let $R_1$ and $R_2$ be regular sets defined over the alphabet, then $ R_1 \cap R_2$ is not regular $R_1 \cup R_2$ is not regular $\Sigma^* - R_1$ is regular $R_1^*$ is not regular
Let $R_1$ and $R_2$ be regular sets defined over the alphabet, then$ R_1 \cap R_2$ is not regular$R_1 \cup R_2$ is not regular$\Sigma^* - R_1$ is regular$R_1^*$ is not re...
User Avatar
5 votes
3 answers
4080
TM Decidablity
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
User Avatar
Page: