Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

27 votes
2 answers
3751
GATE CSE 1990 | Question: 3-vi
Recursive languages are: A proper superset of context free languages. Always recognizable by pushdown automata. Also called type $0$ languages. Recognizable by Turing machines.
Recursive languages are:A proper superset of context free languages.Always recognizable by pushdown automata.Also called type $0$ languages.Recognizable by Turing machine...
User Avatar
1 votes
1 answer
3753
inherent ambiguity
What is inherent ambiguity and does it different from nondeterminism?
What is inherent ambiguity and does it different from nondeterminism?
User Avatar
3 votes
3 answers
3754
Reducibility
If L1 is reducible to L2 and L1 is recursively enumerable then what can we say about L2?
If L1 is reducible to L2 and L1 is recursively enumerable then what can we say about L2?
User Avatar
1 votes
1 answer
3756
regular languages
From S1 can we conclude that on any language if we apply some limit then it would be regular?
From S1 can we conclude that on any language if we apply some limit then it would be regular?
User Avatar
1 votes
2 answers
3757
minimised Automata
Let $L=\{(a^p)^* \mid$ p is a prime number$\}$ and $\Sigma=\{a\}$ .The minimum number of states in NFA that accepts $L$ is?
Let $L=\{(a^p)^* \mid$ p is a prime number$\}$ and $\Sigma=\{a\}$ .The minimum number of states in NFA that accepts $L$ is?
User Avatar
3 votes
1 answer
3758
context free grammar
Is L2 same as a^i b^j c^j , i,j >=0?
Is L2 same as a^i b^j c^j , i,j >=0?
User Avatar
0 votes
0 answers
3760
#Gatebook Qno.26
There is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products, left recursion,). What would be the max number of productions if that gets converted into GNF (A). 2 (B). <=4 (C). <=8 (D). None
There is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products, left recursion,). What would be the max number of...
User Avatar
0 votes
1 answer
3761
#Gatebook Qno.25
Here is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products). What would be the max number of productions if that gets converted into CNF (A). 2 (B). <=4 (C). <=8 (D). None
Here is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products). What would be the max number of productions if th...
User Avatar
0 votes
0 answers
3763
#Gatebook Qno-16
L = {B(N)#B(N+1) : B(N) represents binary pattern for given N. Example B(5)=101, N>=1}. Then which of the following is true for L? (A). L is regular (B). L is CFL but not regular (C). L is Recursive but not CFL (D). L is recursive enumerable but not recursive
L = {B(N)#B(N+1) : B(N) represents binary pattern for given N. Example B(5)=101, N>=1}. Then which of the following is true for L?(A). L is regular(B). L is CFL but not r...
User Avatar
1 votes
1 answer
3766
doubt
plz check which matching true : i got 1st one correct but i am not sure about 2nd ??? 1) Type 1 ------------> Context sensitive grammer 2) Type 1-----------> Recursive
plz check which matching true : i got 1st one correct but i am not sure about 2nd ??? 1) Type 1 Context sensitive grammer 2) Type 1 - Recursive
User Avatar
0 votes
1 answer
3770
DFA minimisation
No of the states in the DFA accepts all the binary strings where no of 0's are divisible by 8 or 4.. What should be the answer..3 or 4?
No of the states in the DFA accepts all the binary strings where no of 0's are divisible by 8 or 4..What should be the answer..3 or 4?
User Avatar
2 votes
1 answer
3771
ME TEST TOC
User Avatar
0 votes
1 answer
3772
ME test
User Avatar
1 votes
1 answer
3773
complement of (0+1)*
What will be the complement of (0+1)*...Is it {}=ϕ or {ϕ}. And also what is the difference between the two?
What will be the complement of (0+1)*...Is it {}=ϕ or {ϕ}.And also what is the difference between the two?
User Avatar
0 votes
1 answer
3775
Empty language
How to prove that a particular machine (FA,PDA,LBA) accepts empty language(φ)?
How to prove that a particular machine (FA,PDA,LBA) accepts empty language(φ)?
User Avatar
0 votes
0 answers
3776
closure properties
I think the question is wrong , it is related to closure properties of NP problems and NP problems are recursive so closed under concatenation, intersection, union, set difference. Correct me if i am wrong..
I think the question is wrong , it is related to closure properties of NP problems and NP problems are recursive so closed under concatenation, intersection, union, set d...
User Avatar
2 votes
1 answer
3777
Recursive language
User Avatar
1 votes
1 answer
3778
Complexity
How to decide the complexity of any language?
How to decide the complexity of any language?
User Avatar
Page: