Register
Webpage for Theory of Computation:

Recent questions tagged theory-of-computation

3 votes
2 answers
3932
No of DFA
How many number of FA are possible with N states (Q1,Q1,........Qn) for input alphabet {1,2,3,........m} ,where Q1 is always initial state ?
How many number of FA are possible with N states (Q1,Q1,........Qn) for input alphabet {1,2,3,........m} ,where Q1 is always initial state ?
User Avatar
3 votes
3 answers
3933
DFA
How many number of DFA's are possible with 2 states X and Y for input alphabet {0,1}?
How many number of DFA's are possible with 2 states X and Y for input alphabet {0,1}?
User Avatar
4 votes
2 answers
3934
CFL closure property
$L = \left \{ a^nb^n \ ; n\geq 0 \ , n \neq 20 \right \}$ is (a) a DCFL (b) a recursive set but not CFL (c) a CFL but not DCFL (d) not a CFL
$L = \left \{ a^nb^n \ ; n\geq 0 \ , n \neq 20 \right \}$ is(a) a DCFL(b) a recursive set but not CFL(c) a CFL but not DCFL(d) not a CFL
User Avatar
8 votes
3 answers
3936
DFA
Construct a minimal DFA which accepts set of all strings over {a,b} such that second symbol from RHS is 'a'.
Construct a minimal DFA which accepts set of all strings over {a,b} such that second symbol from RHS is 'a'.
User Avatar
4 votes
1 answer
3939
UGC NET CSE | December 2015 | Part 3 | Question: 23
Match the following $:$ ... $\text{(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)}$
Match the following $:$$\begin{array}{clcl} & \textbf{List – I} & & \textbf{List – II} \\ \text{(a)} & \{a^n b^n \mid n 0\} \text{ is a deterministic } & \text{...
User Avatar
2 votes
2 answers
3940
UGC NET CSE | December 2015 | Part 3 | Question: 22
The family of context sensitive languages is _____ under union and ____ under reversal closed, not closed not closed, not closed closed, closed not closed, closed
The family of context sensitive languages is _____ under union and ____ under reversalclosed, not closednot closed, not closedclosed, closednot closed, closed
User Avatar
4 votes
3 answers
3944
Regular Languages
If $L1$ and $L1\cap L2$ are regular then $L2$ has to be regular $L2$ need not be regular $L2$ has to be context free None
If $L1$ and $L1\cap L2$ are regular then$L2$ has to be regular$L2$ need not be regular$L2$ has to be context freeNone
User Avatar
1 votes
2 answers
3945
Toc -regular
If L is a regular Language and R is any language such that L+R is regular,then R is a)Must be regular b)May or may not be regular c)Must be non regular language d)Must be CFL
If L is a regular Language and R is any language such that L+R is regular,then R isa)Must be regularb)May or may not be regularc)Must be non regular languaged)Must be CFL...
User Avatar
2 votes
2 answers
3946
Toc -regular
Which of the following statements are true? 1)The union of 2 non regular languages is non regular. 2)The intersection of 2 non regular languages is non regular. a) 1 only b) 2 only c)both d)none
Which of the following statements are true?1)The union of 2 non regular languages is non regular.2)The intersection of 2 non regular languages is non regular.a) 1 onlyb) ...
User Avatar
3 votes
1 answer
3947
Toc - Regular
Consider the language L={0p |p is a prime number} over the alphabet {0} . State whether the following statement is true or false? L is not regular but L* is regular? The cardinality of set (L*)' is 1.
Consider the language L={0p |p is a prime number} over the alphabet {0} .State whether the following statement is true or false?L is not regular but L* is regular?The ca...
User Avatar
1 votes
1 answer
3948
TOC-regular languages
L1 = {apbq | p+q>=106} p,q, can only belong to set N. L1 Regular or not? Complement of L1 is definitely regular,so this should be regular,but it is confusing?
L1 = {apbq | p+q>=106} p,q, can only belong to set N.L1 Regular or not?Complement of L1 is definitely regular,so this should be regular,but it is confusing?
User Avatar
2 votes
2 answers
3949
Toc -Regular or cfl
{0p0q+ 1p1q | 0<=p<=q } Regular or Cfl? My confusion is there is comparison involved between p and q ?
{0p0q+ 1p1q | 0<=p<=q } Regular or Cfl?My confusion is there is comparison involved between p and q ?
User Avatar
2 votes
2 answers
3951
Toc-Recursively Ennumerable
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A. True or false.Cite with reasons.
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A.True or false.Cite with reasons.
User Avatar
3 votes
1 answer
3957
UGC NET CSE | December 2014 | Part 3 | Question: 62
Match the following $:$ ... $\text{a-iv, b-i, c-ii, d-iii}$ $\text{a-i, b-iv, c-iii, d-ii}$
Match the following $:$ $\begin{array} {clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.}& \text{Context free grammar} & \text{i.} & \text{Linear bounded a...
User Avatar
5 votes
3 answers
3958
Theory Of Computation, Chapter 2, Exercises 2 (e) Minimal DFA
Construct a minimal DFA for the given language. How to find the union of two DFA's ?
Construct a minimal DFA for the given language.How to find the union of two DFA's ?
User Avatar
3 votes
2 answers
3960
UGC NET CSE | Junet 2015 | Part 3 | Question: 20
The regular expression corresponding to the language L where $L=\{ x \in \{0,1\}^* \mid x \text{ ends with 1 and does not contain substring 00} $ is (1+01)* (10+01) (1+01)* 01 (1+01)* (1+01) (10+01)* 01
The regular expression corresponding to the language L where $L=\{ x \in \{0,1\}^* \mid x \text{ ends with 1 and does not contain substring 00} $ is(1+01)* (10+01)(1+01)*...
User Avatar
Page: