The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
0
votes
1
answer
1
Self Doubt in checking whether a language is regular or not
asked
2 days
ago
in
Theory of Computation
by
rohan.1737
(
81
points)

38
views
theoryofcomputation
regularlanguages
0
votes
1
answer
2
Regular languages
Kindly give the reason behind 2 and 3?
asked
2 days
ago
in
Theory of Computation
by
Ajit J
(
57
points)

36
views
regularlanguages
theoryofcomputation
0
votes
0
answers
3
TOC, REL
Set of all languages that are not Recursively Enumerable is uncountable. This is true. WHY?
asked
3 days
ago
in
Theory of Computation
by
manisha11
(
199
points)

6
views
theoryofcomputation
turingmachine
0
votes
0
answers
4
RE Ques
Represent the language over ∑={0,1} containing all possible combinations of 0's and 1's but not having two consecutive 0's.
asked
5 days
ago
in
Theory of Computation
by
Devshree Dubey
Boss
(
13.3k
points)

32
views
regularexpressions
theoryofcomputation
0
votes
2
answers
5
RE Ques
Describe in simple English the language represented by the regular expression r=(1+10)*
asked
5 days
ago
in
Theory of Computation
by
Devshree Dubey
Boss
(
13.3k
points)

43
views
regularexpressions
theoryofcomputation
0
votes
1
answer
6
Regular Expression
How do we derive a regular expression from a given language?
asked
5 days
ago
in
Theory of Computation
by
Devshree Dubey
Boss
(
13.3k
points)

9
views
theoryofcomputation
regularexpressions
0
votes
1
answer
7
TOC  Doubt
Choose the correct statement. A class of languages that is closed under A. Intersection and complementation has not to be closed under union B. Union and complementation has to be closed uneer intersection C. Union and intersection has to be closed under complementation. D. Both B and C
asked
5 days
ago
in
Theory of Computation
by
Sumit Singh Chauhan
Junior
(
943
points)

18
views
theoryofcomputation
decidability
0
votes
0
answers
8
TOC  Doubt
The logic of pumping leema is good example of The Pigeon Hole Principle. Can anyone please explain this?
asked
5 days
ago
in
Theory of Computation
by
Sumit Singh Chauhan
Junior
(
943
points)

7
views
theoryofcomputation
regularlanguages
pumpinglemma
0
votes
1
answer
9
TOC  Doubt
As we know that the regular languages are closed under complement. That means if L is regular than it's complement will also be regular. What about the non regular languages? Are they closed under complement? Can we say that if L is non regular than it's complement will also be not regular? Please explain.
asked
5 days
ago
in
Theory of Computation
by
Sumit Singh Chauhan
Junior
(
943
points)

13
views
theoryofcomputation
regularlanguages
decidability
0
votes
0
answers
10
String Operation
While performing a Transpose operation on a string,is it similar to the reverse operation on string or a palindromme?
asked
Aug 13
in
Theory of Computation
by
Devshree Dubey
Boss
(
13.3k
points)

19
views
theoryofcomputation
0
votes
0
answers
11
Curiousity
In an intersection between a regular language and a DCFL, we always tend to promote regular language to DCFL and say that the result will be intersection between DCFL and DCFL but since DCFLs are not closed under intersection we say the result will be a CFL. But ... which is not DCFL Can you write a language which is an intersection between a DCFL and a regular language but not a DCFL.
asked
Aug 12
in
Theory of Computation
by
Vikas Verma
Junior
(
989
points)

36
views
theoryofcomputation
dcfl
regularlanguages
0
votes
1
answer
12
Regular Language
asked
Aug 12
in
Theory of Computation
by
jatinkumar
(
219
points)

45
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
0
votes
1
answer
13
testbook test
Doubt 1: according to me L1 should be subset of L2. But answer is d) L1,L2,L3 are incomparable. Please explain this question to me Doubt 2: which type of language is L4?
asked
Aug 12
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.9k
points)

30
views
testbooktestseries
theoryofcomputation
pushdownautomata
0
votes
0
answers
14
TOC, RL
Consider the following S1: Pumping lemma is used to prove, that particular language is not regular S2: For all DCFL there exist LR(k) grammar but LL(k) may not exist. Which of the above statements are true? (a) Only S1 (b) Only S2 (c) Only S1 and S2 (d) None of these
asked
Aug 10
in
Theory of Computation
by
manisha11
(
199
points)

19
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
2
answers
15
TOC, RL
Consider the following language L = {w ∈ (a+b)*  w has atleast as many occurrences of (bba)’s as (abb)’s}. Which of the following statements is/are true? S1: Language L is regular. S2: Complement of L is CFL. S3: Complement of L is CSL. S4: Reversal of L is CFL.
asked
Aug 10
in
Theory of Computation
by
manisha11
(
199
points)

18
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
0
answers
16
Theory Of Computation , Decidability
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True? (a) If L ≤ pL’ and L’ is semidecidable then L is semidecidable. (b) If L ≤ pL’ and L is RE then L’ is RE. (c) If L ≤ pL’ and L is decidable then L’ decidable. (d) If L ≤ pL’ and L is recursive. Solution: Option (a) PLEASE Explain
asked
Aug 10
in
Theory of Computation
by
manisha11
(
199
points)

11
views
theoryofcomputation
decidability
turingmachine
0
votes
1
answer
17
Testbook test series
Is this given answer correct?
asked
Aug 7
in
Theory of Computation
by
Avik Chowdhury
Junior
(
737
points)

35
views
theoryofcomputation
0
votes
0
answers
18
Regular language
$L=\left \{ a^{n}:\text{n is the product of two prime number} \right \}$$L$ is regular or non regular?
asked
Aug 3
in
Theory of Computation
by
saumya mishra
Active
(
1.2k
points)

56
views
theoryofcomputation
regularlanguages
0
votes
0
answers
19
Regular language
Whether the language $L=\left \{ a^{n}b^{l}a^{k}:n+l+k> 5 \right \}$ is regular or not???
asked
Aug 3
in
Theory of Computation
by
saumya mishra
Active
(
1.2k
points)

37
views
theoryofcomputation
dcfl
+2
votes
3
answers
20
TOC self doubt
$\text{Is the language L is DCFL or CFL ?}$
asked
Aug 3
in
Theory of Computation
by
Prince Sindhiya
Active
(
2.3k
points)

58
views
theoryofcomputation
contextfreelanguages
0
votes
0
answers
21
self doubt
which of the following is correct: 1. countable sets are closed under union. 2. countable sets are closed under intersection. 3. countable sets are closed under set difference. 4. countable sets are closed under kleene closure. 5. countable sets are closed under concatenation. 6. countable sets are closed under complementation.
asked
Aug 3
in
Theory of Computation
by
ds2905902
(
27
points)

21
views
theoryofcomputation
+1
vote
1
answer
22
Made Easy Theory Book
Can somebody please explain the meaning of the following statement : An automation is a cognitive device and a grammar is a generative device.
asked
Aug 1
in
Theory of Computation
by
Sid865
(
51
points)

40
views
theoryofcomputation
selfdoubt
finiteautomata
0
votes
2
answers
23
Regular expression
Is a*b* + b*a* = ( a + b)* ______
asked
Jul 31
in
Theory of Computation
by
Ajaaz
(
17
points)

78
views
theoryofcomputation
regularexpressions
finiteautomata
nfa
0
votes
2
answers
24
Theory of Computation
Can someone please help me understand these two points about minimum DFA and Minimum NFA, thank you
asked
Jul 31
in
Theory of Computation
by
Ajaaz
(
17
points)

32
views
nfa
#dfa
finiteautomata
theoryofcomputation
minimum
numberofdfa
0
votes
1
answer
25
Gate overflow old question
Referring to the question https://gateoverflow.in/227957/selfdoubt If the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular language?
asked
Jul 31
in
Theory of Computation
by
Vikas Verma
Junior
(
989
points)

39
views
theoryofcomputation
turingmachine
finiteautomata
0
votes
0
answers
26
#Regular Language
Consider the set of all words over the alphabet {x, y, z} where the number of y’s is not divisible by 2 or 7 and no x appears after a z. This language is: (A) regular (B) not known to be regular (C) contextfree but not regular (D) recursively enumerable but not contextfree
asked
Jul 30
in
Theory of Computation
by
himgta
Active
(
1.1k
points)

24
views
theoryofcomputation
regularlanguages
0
votes
0
answers
27
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ? I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
asked
Jul 28
in
Theory of Computation
by
Matrix
(
59
points)

25
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dpda
0
votes
1
answer
28
GATE CS  TOC AUTOMATA
asked
Jul 28
in
Theory of Computation
by
AnkurGarg
(
93
points)

29
views
theoryofcomputation
gate
automata
0
votes
0
answers
29
GATE CS  TOC AUTOMATA
asked
Jul 28
in
Theory of Computation
by
AnkurGarg
(
93
points)

27
views
gate
cs

theoryofcomputation
automata
theoryofcomputation
badquestion
+1
vote
0
answers
30
GATE CS  TOC AUTOMATA
asked
Jul 28
in
Theory of Computation
by
AnkurGarg
(
93
points)

18
views
gate
cs

theoryofcomputation
automata
Page:
1
2
3
4
5
6
...
81
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Anxiety
Nielit 2018
Donation (Kerala Flood)
Schedule for GATE 2019
GATE 2019 official website
Follow @csegate
Gatecse
Recent questions tagged theoryofcomputation
Recent Blog Comments
Thanx Mk utkarsh and nikhil bro ... i really ...
Firstly I am not topper. or ranker.
but ...
If you are not able to understand the concept of ...
done:)
Thanx man ... i really appreciate it ...
38,187
questions
45,688
answers
132,723
comments
49,654
users