Facebook Login
Login
Register
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent Posts
Some Good courses on System Development
My GATE preparation experience (GATE CS 2020 AIR-13)
GATE CSE: IIST Admissions
GATE CSE: IIITH Admissions
Video Solution for Previous Year GATE Questions
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(8.4k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.6k)
Others
(2k)
Admissions
(595)
Exam Queries
(573)
Tier 1 Placement Questions
(23)
Job Queries
(72)
Projects
(18)
Follow @csegate
Recent questions and answers in Theory of Computation
Recent Blog Comments
50% as in 120 or the 50% of total number of...
congrats!. Best of luck for your next endeavour.
What is the average package offered to mtech cse...
congrats very much
Congratulations ! Indeed Previous year questions...
Recent questions and answers in Theory of Computation
0
votes
6
answers
1
513
views
Peter Linz Edition 4 Exercise 2.1 Question 6 (Page No. 47)
With $Σ = $ {$a,b$} , give a dfa for $L =$ {$w_1aw_2: |w1|≥ 3, |w2|≤ 5$}.
answered
May 6
in
Theory of Computation
by
NARAYANA
(
21
points)
513
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+33
votes
7
answers
2
3.7k
views
GATE2008-52
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$
answered
May 1
in
Theory of Computation
by
Omthakur1224
(
15
points)
3.7k
views
gate2008
theory-of-computation
finite-automata
normal
0
votes
1
answer
3
27
views
Peter Linz Edition 4 Exercise 3.1 Question 21 (Page No. 77)
Give a general method by which any regular expression $r$ can be changed into $\widehat{r}$ such that $(L(r))^R = L(\widehat{r})$.
answered
Apr 25
in
Theory of Computation
by
Ddutta
(
11
points)
27
views
peter-linz
peter-linz-edition4
theory-of-computation
regular-expressions
0
votes
1
answer
4
343
views
Post correspondence problem
answered
Apr 19
in
Theory of Computation
by
darshansharma_
(
173
points)
343
views
theory-of-computation
+1
vote
2
answers
5
117
views
Peter Linz, 3rd Ed, Chapter 1, Pg 15, Ques 19
if f(n) = O(n2) and g(n) = O(n3), then what is the complexity of f(n)*g(n) and f(n)/g(n) in big-o-notation?
answered
Apr 18
in
Theory of Computation
by
sakharam
Active
(
3.1k
points)
117
views
theory-of-computation
asymptotic-notations
0
votes
3
answers
6
144
views
CFL or CSL
Let L = $\{ a^n b^m | m , n \in \textbf{N} \text{ and m is multiple of n}\}$ How do we prove that this language is not CFL.
answered
Apr 7
in
Theory of Computation
by
Raju2021
(
57
points)
144
views
theory-of-computation
context-free-languages
context-sensitive-languages
+2
votes
3
answers
7
536
views
UGCNET-June-2019-II-75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$
answered
Apr 5
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
536
views
ugcnetjune2019ii
finite-automata
minimal-state-automata
+2
votes
3
answers
8
393
views
ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
answered
Apr 5
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
393
views
isro-2020
theory-of-computation
finite-automata
normal
0
votes
1
answer
9
39
views
UGCNET-Dec2007-II: 5
Consider a Moore machine M whose digraph is : Then L(M), the language accepted by the machine M, is the set of all strings having : two or more b’s. three or more b’s. two or more a’s. three or more a’s.
answered
Apr 4
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
39
views
ugcnetdec2007ii
+1
vote
1
answer
10
47
views
NIELIT 2016 MAR Scientist B - Section C: 27
If $L$ be a language recognizable by a finite automaton, then language from $\text{{L}}$={$w$ such that $w$ is a prefix of $v$ where $v\in L$}, is a regular language. context-free language. context-sensitive language. recursive enumeration language.
answered
Apr 3
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
47
views
nielit2016mar-scientistb
+1
vote
1
answer
11
57
views
NIELIT 2016 MAR Scientist B - Section C: 25
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to ... to deterministic push-down automata. Multi-tape Turing machines are equivalent to single-tape Turing machines.
answered
Apr 3
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
57
views
nielit2016mar-scientistb
+1
vote
2
answers
12
138
views
theory of computtion
find regular expression of 1. S-> 01A/10B A->0B/1 B->1A/0 and 2. A->A00 /A1/0 3. S->baS/aA A->bbA/bb
answered
Apr 3
in
Theory of Computation
by
Raju2021
(
57
points)
138
views
regular-expressions
grammar
0
votes
2
answers
13
52
views
UGCNET-Dec2006-II: 1
Which of the regular expressions corresponds to this grammar ? $S → AB/AS, A → a/aA, B → b$ $aa^*b^+$ $aa^*b$ $(ab)^*$ $a(ab)^*$
answered
Apr 2
in
Theory of Computation
by
immanujs
Active
(
1.4k
points)
52
views
ugcnetdec2006ii
0
votes
1
answer
14
33
views
NIELIT 2016 DEC Scientist B (CS) - Section B: 24
Given two DFA's $M1$ and $M2$. They are equivalent if: $M1$ and $M2$ has the same number of states. $M1$ and $M2$ accepts the same language i.e $L(M1)=L(M2)$. $M1$ and $M2$ has the same number of final states. None of the above.
answered
Apr 2
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
33
views
nielit2016dec-scientistb-cs
0
votes
1
answer
15
49
views
NIELIT 2016 DEC Scientist B (CS) - Section B: 6
Which of the following is wrong? Turing machine is a simple mathematical model of general purpose computer. Turing machine is more powerful than finite automata. Turing Machine can be simulated by a general purpose computer. All of these.
answered
Apr 2
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
49
views
nielit2016dec-scientistb-cs
+1
vote
1
answer
16
40
views
NIELIT 2016 DEC Scientist B (CS) - Section B: 3
If $L1$ is CFL and $L2$ is regular language which of the following is false? $L1-L2$ is not context free. $L1$ intersection $L2$ is context free. $\text{~} L1$ is context free. Both (A) and (C).
answered
Apr 2
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
40
views
nielit2016dec-scientistb-cs
0
votes
1
answer
17
36
views
UGCNET-Dec2007-II: 3
A context free grammar is : type $0$. type $1$. type $2$. type $3$.
answered
Apr 2
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
36
views
ugcnetdec2007ii
0
votes
1
answer
18
30
views
NIELIT 2016 MAR Scientist B - Section C: 29
The CFG $S →aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$ $(a+b)(a+b)^*$ $(a+b)(a+b)$ all of these
answered
Mar 31
in
Theory of Computation
by
haralk10
Active
(
1.6k
points)
30
views
nielit2016mar-scientistb
+1
vote
1
answer
19
46
views
NIELIT 2016 MAR Scientist B - Section C: 26
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language? $L_1L_2$ $L_1\cap L_2$ $L_1\cap R$ $L_1\cup L_2$
answered
Mar 31
in
Theory of Computation
by
vg653
Junior
(
639
points)
46
views
nielit2016mar-scientistb
+1
vote
1
answer
20
72
views
NIELIT 2016 MAR Scientist B - Section C: 24
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet ${a,b}$? $a^*b^*$ $(a\mid b)^*$ $(ab)^+$ $(a\mid b^*)$
answered
Mar 31
in
Theory of Computation
by
haralk10
Active
(
1.6k
points)
72
views
nielit2016mar-scientistb
0
votes
0
answers
21
35
views
NIELIT 2016 MAR Scientist B - Section C: 28
Which of the following statements is correct? $A={a^nb^n\mid n= 0,1,2,3\dots}$ is regular language. Set $B$ of all strings of equal number of $a$'s and $b$'s defines a regular language. $L(A^*B^*) \cap B$ gives the set $A$. None of these.
asked
Mar 31
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
63.5k
points)
35
views
nielit2016mar-scientistb
+1
vote
1
answer
22
56
views
NIELIT 2016 DEC Scientist B (CS) - Section B: 1
Palindromes can't be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the matches the first half. All of the above.
answered
Mar 31
in
Theory of Computation
by
Bhargav D Dave 6
(
329
points)
56
views
nielit2016dec-scientistb-cs
0
votes
0
answers
23
27
views
NIELIT 2017 July Scientist B (CS) - Section B: 48
What is the complement of the language accepted by the NFA shown below? $\phi$ $\{\epsilon\}$ $a^*$ $\{a,\epsilon\}$ $1$ $2$ $3$ $4$
asked
Mar 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
63.5k
points)
27
views
nielit2017july-scientistb-cs
0
votes
1
answer
24
64
views
Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa’s?
answered
Mar 28
in
Theory of Computation
by
Wilbred Anto
(
21
points)
64
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+1
vote
1
answer
25
367
views
Recognize the language
If L be a language recognizable by a finite automata, then language from {L}={w such that w is prefix of v where v belongs to L},is a a. Regular Language b. Context Free language c. Context Sensitive Language d. Recursive Enumerable Language
answered
Mar 28
in
Theory of Computation
by
habedo007
Active
(
3.1k
points)
367
views
+1
vote
1
answer
26
336
views
REGULAR EXPRESSION - Inverse homomorphism
Let r = (10 + 0) * 11(0 + 1) * be a regular expression for the regular language L and let h(0) = ab and h(1) = ba a homomorphism. What is a regular expression for h(L)? How about h −1 (L′) if L′ is given by the regular expression r ′ = (ab + a) * bb(a + b) *?
answered
Mar 27
in
Theory of Computation
by
Raju2021
(
57
points)
336
views
theory-of-computation
regular-expressions
regular-languages
0
votes
1
answer
27
36
views
UGCNET-Dec2004-II: 3
The context-free languages are closed for : Intersection Union Complementation Kleene Star (i) and (iv) (i) and (iii) (ii) and (iv) (ii) and (iii)
answered
Mar 26
in
Theory of Computation
by
Shobhit Joshi
Loyal
(
5.5k
points)
36
views
ugcnetdec2004ii
0
votes
0
answers
28
35
views
UGCNET-Jan2017-III: 61
Given the following two statements: $L=\{w\mid n_{a}(w)=n_{b}(w)\}$ is deterministic context free language, but not linear. $L=\{a^{n}b^{n}\} \cup \{a^{n}b^{2n} \}$ is linear, but not deterministic context free language. Which of the following options is correct? Both (A) and (B) are false. Both (A) and (B) are true. (A) is true, (B) is false. (A) is false, (B) is true.
asked
Mar 24
in
Theory of Computation
by
jothee
Veteran
(
109k
points)
35
views
ugcnetjan2017iii
identify-class-language
0
votes
5
answers
29
298
views
NIELIT Scientist-B Dec 2017_53
What is the meaning of regular expression $\sum$* 001 $\sum$* ? (A) Any string containing '1' as substring (B) Any string containing '01' as substring (C) Any string containing '011' as substring (D) All string containing '001' as substring
answered
Mar 23
in
Theory of Computation
by
Vipin Tiwari
(
405
points)
298
views
0
votes
4
answers
30
272
views
NIELIT Scientist-B Dec 2017_54
According to the given language, which among the following expressions does it corresponds to ? Language L={$x \epsilon${0,1}|$x$ is of length 4 or less} (A) (0+1+0+1+0+1+0+1)4 (B) (0+1)4 (C) (01)4 (D) (0+1+$\epsilon$)4
answered
Mar 23
in
Theory of Computation
by
Vipin Tiwari
(
405
points)
272
views
+1
vote
3
answers
31
207
views
ISRO2020-37
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
answered
Mar 20
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
207
views
isro-2020
theory-of-computation
context-free-languages
easy
0
votes
4
answers
32
339
views
NIELIT Scientist-B Dec 2017_59
Which of the following statement is true ? (A) Deterministic context free language are closed under complement (B) Deterministic context free language are not closed under complement (C) Deterministic context free language are closed under intersection with with regular set (D) All of the options
answered
Mar 20
in
Theory of Computation
by
Vipin Tiwari
(
405
points)
339
views
0
votes
4
answers
33
1.1k
views
NIELIT Scientist-B Dec 2017_60
Which of the following is true ? (A) Mealy and Moore machine are language acceptors (B) Finite State automata is language translator (C) NPDA is more powerful than DPDA (D) Mealy machine is more powerful than Mealy machine
answered
Mar 20
in
Theory of Computation
by
Vipin Tiwari
(
405
points)
1.1k
views
0
votes
1
answer
34
69
views
Toc me test me me
Minimum ba how can accept?
answered
Mar 19
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
69
views
+2
votes
3
answers
35
1.4k
views
GATE2020-CS-10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
answered
Mar 19
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
1.4k
views
gate2020-cs
theory-of-computation
+1
vote
4
answers
36
1.1k
views
GATE2020-CS-8
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ
answered
Mar 19
in
Theory of Computation
by
smsubham
Boss
(
17.1k
points)
1.1k
views
gate2020-cs
theory-of-computation
+1
vote
1
answer
37
214
views
NIELIT Scientist-B Dec 2017_30
Let G be a grammar in CFG and let W1,W2 $\epsilon$ L(G) such that |W1|=|W2| then which of the following statement is true ? (A) Any derivation of W1 has exactly the same number of steps as any derivation of W2 (B) Different derivation have different length (C) Some derivation of W1 may be shorter the derivation of W2 (D) None of the options
answered
Mar 19
in
Theory of Computation
by
topper98
Junior
(
605
points)
214
views
+1
vote
3
answers
38
297
views
NIELIT Scientist-B Dec 2017_40
A regular expression is (a+b*c) is equivalent to : (A) set of strings with either a or one or more occurrence of b followed by c. (B) (b*c+a) (C) set of strings with either a or zero or more occurrence of b followed by c. (D) Both (B) and (C)
answered
Mar 19
in
Theory of Computation
by
topper98
Junior
(
605
points)
297
views
0
votes
3
answers
39
198
views
NIELIT Scientist-B Dec 2017_7
The collection of Turing recognizable language is closed under: (i) Union (ii) Intersection (iii) Complement (iv) Concatenation (v) Star closure (A) (i) Only (B) Both (i), (iv) (C) (i),(ii),(iv) and (v) (D) All of the options
answered
Mar 19
in
Theory of Computation
by
topper98
Junior
(
605
points)
198
views
+1
vote
3
answers
40
99
views
NIELIT July 2017_120
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE ? A) L1' is recursive and L2' is recursively enumerable B) L1' is recursive and L2' is not recursively enumerable C) L1' and L2' are recursively enumerable D) L1' is recursively enumerable and L2' is recursive
answered
Mar 19
in
Theory of Computation
by
anurag sharma
(
363
points)
99
views
To see more, click for all the
questions in this category
.
...