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
Questions without answers in Theory of Computation
No answer
No selected answer
No upvoted answer
Featured
Previous GATE
Web Page
Regular expressions
and
finite automata,
Contextfree grammars
and
pushdown automata,
Regular
and
contextfree languages,
Pumping lemma,
Turing machines
and
undecidability.
No answer
No selected answer
No upvoted answer
Featured
Previous GATE
0
votes
0
answers
1
Decidable
All P, NP and NPC problems are turing decidable problems. CFLs are in NP area and CFL's are not closed under intersection and complementation. So does it mean that CFL's are undecidable under intersection and complementation. If CFL is undecidable on intersection and complementation then how NP problems can be turing decidable?
asked
19 hours
ago
in
Theory of Computation
by
!KARAN
(
299
points)

5
views
0
votes
0
answers
2
Test series
Can someone explain this problem? Thanks in advance
asked
1 day
ago
in
Theory of Computation
by
Kalpataru Bose
(
337
points)

21
views
madeeasytestseries
testbooktestseries
theoryofcomputation
regularexpressions
0
votes
0
answers
3
Peter linz
Input alphabet {a,b} give a dfa for L= w1a w2 where w1>=3,w2<=5. (Unit 2 exercise 6 problem)
asked
2 days
ago
in
Theory of Computation
by
Harshitha 123
(
81
points)

15
views
theoryofcomputation
peterlinz
0
votes
0
answers
4
Finite Automata
Whenever it is mentioned to derive minimal finite automata. We should go with DFA or NFA?
asked
2 days
ago
in
Theory of Computation
by
jaisyking
(
7
points)

20
views
0
votes
0
answers
5
Decision properties of finite automata
Is equivalence problem decidable problem or not?
asked
3 days
ago
in
Theory of Computation
by
Harshitha 123
(
81
points)

22
views
theoryofcomputation
finiteautomata
0
votes
0
answers
6
Theory of computation
What is grid automata (m+1)(n+1) state calculation? (For some question asked from Peter Linz unit 2 exercise 2(d) the answer is given as" it is like grid automata and to calculate number of states we can use (m+1)(n+1) if we require m a's and n b's" and the question is "all strings with at least one 'a' and exactly 2b's" )
asked
4 days
ago
in
Theory of Computation
by
Harshitha 123
(
81
points)

20
views
finiteautomata
theoryofcomputation
+1
vote
0
answers
7
ISRO CS 17
Consider the following statements about the context free grammar G = {S>SS , S>ab , S>ba , S>^} I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which combination below expresses all ... ? A) I only B) I and III C) II and II D) All I,II,III In a answer key shown answer D but II is not right.
asked
5 days
ago
in
Theory of Computation
by
Nikhil Patil
(
353
points)

30
views
userisro2017
usermod
theoryofcomputation
dcfl
dpda
0
votes
0
answers
8
Regular Expression DFA
Regular Expression for this DFA: (a) (b + aa)* ab(a + b)* (b) b*a (ab*a)* b(a + b)* (c) Both (a) and (b) (d) b* ab(a + b)*
asked
5 days
ago
in
Theory of Computation
by
Sanjay Sharma
Boss
(
48.1k
points)

44
views
0
votes
0
answers
9
Minimal dfa
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)
asked
6 days
ago
in
Theory of Computation
by
Harshitha 123
(
81
points)

23
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
0
votes
0
answers
10
Peter Linz
Design a DFA over {0,1} a)Strings containing 00 but not 000 b)strings in which 00 is immediately followed by atleast one 1 c) strings in which leftmost 2 symbols and rightmost two symbols are identical d)strings in which leftmost 2 symbols and rightmost 2 symbols are different
asked
Jun 9
in
Theory of Computation
by
Sourav_35
(
199
points)

27
views
theoryofcomputation
peterlinz
+1
vote
0
answers
11
Theory of computation
asked
Jun 6
in
Theory of Computation
by
Prince Sindhiya
Junior
(
637
points)

30
views
regularlanguages
+1
vote
0
answers
12
Theory of computation
asked
Jun 6
in
Theory of Computation
by
Prince Sindhiya
Junior
(
637
points)

18
views
regularlanguages
+1
vote
0
answers
13
Introduction to Automata Theory Properties of regular Languages  Q 4.2.10
asked
Jun 6
in
Theory of Computation
by
Savvy
(
17
points)

27
views
theoryofcomputation
regularlanguages
+1
vote
0
answers
14
Pda Automata
Why only stack data structure is used for implementing pushdown automata(pda) why not others ???
asked
Jun 3
in
Theory of Computation
by
vijju532
(
55
points)

24
views
theoryofcomputation
pushdownautomata
+1
vote
0
answers
15
Introduction to Computer Theory
Construct a Turing Machine to compute the following function: $$f(x,y) = 1 \text{ if length(x) > length(y)} \\ =0 \text{ otherwise}{}$$ where $x$ and $y$ are strings over the alphabet set $\{a b\}$. The output should be written on the tape after a \$. For example, if input is $\$abaab\$aaba$, then output should be $\$abaab\$aaba\$1$
asked
May 30
in
Theory of Computation
by
The Capricorn
(
147
points)

27
views
theoryofcomputation
turingmachine
0
votes
0
answers
16
Introduction to Computer Theory
Construct a Turing Machine that computes length of a given input string. For Example, if the input is $abbaab$, the output should be $abbaab00110$.
asked
May 28
in
Theory of Computation
by
The Capricorn
(
147
points)

21
views
theoryofcomputation
turingmachine
0
votes
0
answers
17
TOC Language is CFL or not
xx^r /x=[0,1]* , x=l Here we have restriction that on length of x should be exactly l If only the language is given How can we say that l is finite or infinite In one of the videos they have taken subsets of l also 2^l , how can this language be Regular and CFL plzz explain each point properly
asked
May 17
in
Theory of Computation
by
sanju77767
(
151
points)

26
views
0
votes
0
answers
18
regular language and CFL
$L=\left \{ a^{n}b^{n}c^{n}d^{n}  n<10^{10} \right \}$ I know this language is regular language so it is DCFL AND CFL also but how can we implenment this language with DCFL with stack because till we reach c there will ... can be implemented using FA We can have these many states to compare how we will compare in stack explain the logic of this language with DCFL
asked
May 17
in
Theory of Computation
by
sanju77767
(
151
points)

38
views
theoryofcomputation
dcfl
0
votes
0
answers
19
Context Free Grammar
What is NonInheritant grammar and inheritant Grammar? Please explain with an example.
asked
May 14
in
Theory of Computation
by
SreenivasaRaju
(
27
points)

21
views
0
votes
0
answers
20
what is the regular expression and design dfa and nfa for arthimatic expression
asked
May 13
in
Theory of Computation
by
doaa
(
31
points)

70
views
finiteautomata
theoryofcomputation
regularexpressions
dfa
nfa
0
votes
0
answers
21
FA to Regular Expression: when no two a's and no two b's should come together
asked
May 9
in
Theory of Computation
by
surbhijain93
(
31
points)

89
views
theoryofcomputation
regularexpressions
finiteautomata
+1
vote
0
answers
22
TOC language is CFL or not
L={a^n,b^n,c^m / n>m} we have to compare n and m everywhere I know till we reach b there will be nothing in the stack BUT generally we can make this language if possible suppose when we are putting one a into the stack suppose we put Two a's ... string I'm asking this question because in one of the video for the question we were taking two a's on behalf of one .......
asked
May 7
in
Theory of Computation
by
sanju77767
(
151
points)

44
views
0
votes
0
answers
23
TOC PDA machine
Is my PDA correct or not plzz rectify me If I have made a mistake
asked
May 7
in
Theory of Computation
by
sanju77767
(
151
points)

23
views
0
votes
0
answers
24
How to find out the quotient of regular language with example?
asked
May 6
in
Theory of Computation
by
SreenivasaRaju
(
27
points)

36
views
theoryofcomputation
+1
vote
0
answers
25
Peter linz
how to draw dfa for this? L= {w: there are at most two runs of a’s of length three}.
asked
May 3
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.6k
points)

65
views
theoryofcomputation
peterlinz
dfa
0
votes
0
answers
26
TOC questions
L={a^n \ n>=0} M={b^n \ n>=0} L.M is a regular language and the DFA for this is going to be ending with b and epsilon and it will have two states Am I correct or not
asked
May 3
in
Theory of Computation
by
sanju77767
(
151
points)

51
views
0
votes
0
answers
27
kleene method TOC
plzz help to understand this kleene method plzzzz explain properly
asked
Apr 30
in
Theory of Computation
by
sanju77767
(
151
points)

16
views
0
votes
0
answers
28
Moore machine example
plzz expain this machine how it is working machine is Addition of two binary numbers
asked
Apr 30
in
Theory of Computation
by
sanju77767
(
151
points)

48
views
0
votes
0
answers
29
please anyone explain me the concept of utm ,queue automata ,ntm,htm
asked
Apr 30
in
Theory of Computation
by
Rahul Dwivedi
(
9
points)

14
views
0
votes
0
answers
30
can an npda be converted to pda
asked
Apr 30
in
Theory of Computation
by
Rahul Dwivedi
(
9
points)

36
views
To see more, click for the
full list of questions
or
popular tags
.
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
Members at the site
flyingsagar425
Subham Nagar
eyeamgj
Rahul Bhatia
!KARAN
Recent Posts
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Effect of Academic/ Career Gap during Mtech Placements at IIT/NIT
Gate Rank Improvement
All categories
General Aptitude
Engineering Mathematics
Digital Logic
Programming & DS
Algorithms
Theory of Computation
Compiler Design
Operating System
Databases
CO & Architecture
Computer Networks
Non GATE
Others
Admissions
Exam Queries
Tier 1 Placement Questions
Job Queries
Projects
Follow @csegate
Gatecse
Questions without answers in Theory of Computation
Recent Blog Comments
thanks for the info .but qstn 1.4 time complexity ...
What was your GATE rank and score this time ...
finish all subjects first then start taking all ...
@Arjun sir Address Confirmation mail not ...
Those who pay till today  June 17 can expect the ...
36,075
questions
43,521
answers
123,666
comments
42,747
users