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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
Draw PDA for this
L = { a^m b^n c^k=m+n } Please draw PDA for this Language!
asked
18 hours
ago
in
Theory of Computation
by
Guilherme Zanini Mor
(
9
points)

9
views
theoryofcomputation
pushdownautomata
dpda
0
votes
0
answers
2
Decidable
Which one is True? $1)$ A set $S$ , some of it’s elements creates injective function. Then S is decidable $2)$ A bijective function can be $NP$ Hard $3)$ A function which is Recursive Enumerable. Inverse of this function is decidable
asked
1 day
ago
in
Theory of Computation
by
srestha
Veteran
(
103k
points)

25
views
theoryofcomputation
decidability
0
votes
0
answers
3
Draw PDA for this
L = {a^m b^n c^k=m+n }  m >= 0 and n >= 0  Please draw PDA for this Language!
asked
1 day
ago
in
Theory of Computation
by
Guilherme Zanini Mor
(
9
points)

16
views
theoryofcomputation
pushdownautomata
contextfreelanguage
dcfl
0
votes
0
answers
4
Decidability
Match the following 1.P 2.NP 3.NPComplete 4. NPHard 1.Decidable 2.Undecidable
asked
1 day
ago
in
Theory of Computation
by
srestha
Veteran
(
103k
points)

40
views
theoryofcomputation
0
votes
0
answers
5
Context Free Languages
Can we claim that a CFL is closed under complementation by transforming it’s NPDA in a way such that it’s nonfinal states become final states and final states become nonfinal ?
asked
2 days
ago
in
Theory of Computation
by
dnivara
(
15
points)

24
views
0
votes
0
answers
6
Halting problem of TM which recognize recursive languages is undecidable?
asked
2 days
ago
in
Theory of Computation
by
gmrishikumar
(
453
points)

22
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
turingmachine
ricetheorem
0
votes
0
answers
7
Madeeasy
Options: $\left \{ \left ( b^{n}ab^{n}a\right )^{m}  n,m \geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}a\right )^{m}  n,m \geq 0 \right \} \cup \left \{ b^{n}  n\geq 0 \right \}$ $\left \{ \left ( b^{n}ab^{n}\right )^{m}a  n,m \geq 0 \right \}$ $NONE$
asked
2 days
ago
in
Theory of Computation
by
jatin khachane 1
Active
(
3.1k
points)

77
views
madeeasytestseries
theoryofcomputation
0
votes
0
answers
8
pda doubt
Consider the following PDA: The language accepted by the given PDA is: L = {(b^n a b^n a )^m  m, n >= 0} L = {b^n a b^n a  n >= 0} {bn  n >= 0} L = {b^n a b^n a  n >= 0} L = {(b^n a b^n a )^m  m, n >= 0} {bn  n >= 0}
asked
2 days
ago
in
Theory of Computation
by
Satbir
Active
(
1.1k
points)

19
views
pushdownautomata
theoryofcomputation
0
votes
0
answers
9
Reversal of DFA doubt
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state
asked
2 days
ago
in
Theory of Computation
by
aditi19
Active
(
2k
points)

37
views
theoryofcomputation
finiteautomata
#dfa
minimalstateautomata
0
votes
0
answers
10
THEORY OF COMPUTATION
Let $L_1= (0+1)^* , L_2=(01^*0 +1^*) \text{ and } L3=(01^+0 +1^+ + \epsilon) $. If $L=L_1 \cap L_2 \cap L_3$ Then find the number of strings in $L$ which do not contain $11$.
asked
3 days
ago
in
Theory of Computation
by
ROHIT SHARMA 5
(
143
points)

27
views
theoryofcomputation
regularlanguages
0
votes
0
answers
11
made easy 2018
consider the following DFA,which of the following set represents the states which are minimized into single state? (i){q1,q2,q4} (ii){q1,q2,q3} (iii){q1,q3} (iv){q0,q1,q3} i am getting (iii) as answer but given answer is (ii)
asked
3 days
ago
in
Theory of Computation
by
Gate Fever
Active
(
3.4k
points)

18
views
0
votes
0
answers
12
Self doubt
L = { a$^{m}$b$^{n}$ / m < n , m>=0 , n>=1 } Is the language DCFL or CFL ?
asked
3 days
ago
in
Theory of Computation
by
Vipin Rai
(
375
points)

26
views
0
votes
0
answers
13
proving a language is regular based on two regular language over same $\Sigma$ (complicated)
asked
4 days
ago
in
Theory of Computation
by
csenoob
(
21
points)

8
views
regularlanguages
theoryofcomputation
finiteautomata
closureproperty
0
votes
0
answers
14
VirtualGate TOC
Let us say we assume last production rule to be $A \rightarrow \epsilon$ The language generated by the given grammar will be something like $L = \{c, bcb, b^2cb^2, b^3cb^3, \dots\}$. Is this a regular language. Is it possible to construct DFA for L?
asked
4 days
ago
in
Theory of Computation
by
!KARAN
Junior
(
887
points)

22
views
0
votes
0
answers
15
VirtualGate CFL or Regular language Identification
asked
4 days
ago
in
Theory of Computation
by
!KARAN
Junior
(
887
points)

34
views
theoryofcomputation
identifyclasslanguage
0
votes
0
answers
16
made easy 2019
L={a*b*c* – {$a^{n}b^{n}c^{n}$ ;$n\geq 0$} shouldn’t L be recursive?? bcoz $a^{n}b^{n}c^{n}$ is recursive and its complement is also recursive; a*b*c* is regular ; therefore, regular $\cap$ recursive = recursive..
asked
4 days
ago
in
Theory of Computation
by
Gate Fever
Active
(
3.4k
points)

26
views
0
votes
0
answers
17
made easy 2019
Consider the following context free grammar G: S>c/aS/aSbS is G inherently ambiguous?? how to check this??
asked
4 days
ago
in
Theory of Computation
by
Gate Fever
Active
(
3.4k
points)

8
views
0
votes
0
answers
18
made easy 2019
consider the folllowing PDA given below where z0 represents stack symbol: here , even b is getting accepted, so in this n(a) $\ngeqslant$n(b); shouldn’t the answer be none of these??
asked
4 days
ago
in
Theory of Computation
by
Gate Fever
Active
(
3.4k
points)

18
views
+1
vote
0
answers
19
Ace yest seriea
asked
4 days
ago
in
Theory of Computation
by
abhishekmehta4u
Boss
(
24.2k
points)

23
views
+1
vote
0
answers
20
Ace test series
asked
5 days
ago
in
Theory of Computation
by
abhishekmehta4u
Boss
(
24.2k
points)

27
views
0
votes
0
answers
21
#Self doubt GATE 2018
https://gateoverflow.in/204101/gate201827 Please explain statement Q and R
asked
5 days
ago
in
Theory of Computation
by
himgta
Active
(
2.7k
points)

10
views
0
votes
0
answers
22
Self doubt
which is/are TRUE: 1)All recursive lang are decidable problems? 2)All decidable problems are recursive language?  is both of them are true? any proof please?
asked
5 days
ago
in
Theory of Computation
by
pps121
Active
(
1.4k
points)

15
views
decidability
0
votes
0
answers
23
PDA toc
Plz tell me answer of the below question In automaton theory ,a PDA is a variation of: 1)finite automaton that can make use of a stack containing data 2)infinite automaton that can make use of a stack containing data 3)both A and B 4)none of the above
asked
5 days
ago
in
Theory of Computation
by
Shivshankar
(
41
points)

23
views
pushdownautomata
0
votes
0
answers
24
Grammer
Which of the following problem is undecidable? A) membership problem for CFL B) membership problem for regular language C)membership problem for csl D)membership problem for type O language
asked
5 days
ago
in
Theory of Computation
by
Shivshankar
(
41
points)

32
views
theoryofcomputation
grammar
0
votes
0
answers
25
finding equivalence classes $R_L$ of given languages and separating words
asked
5 days
ago
in
Theory of Computation
by
csenoob
(
21
points)

17
views
finiteautomata
equivalenceclasses
myhillnerode
theoryofcomputation
0
votes
0
answers
26
DFA NFA and ambiguity
Why is Regular grammar obtained from DFA always unambiguous? Why Regular grammar obtained from NFA may or may not be ambiguous?
asked
5 days
ago
in
Theory of Computation
by
OneZero
(
251
points)

10
views
theoryofcomputation
nfa
ambiguous
0
votes
0
answers
27
Decidability
Consider the following two decision problems A. Whether a Turing machine takes more than 481 steps on input $\epsilon$ ? B. Whether a Turing machine accepts the null string $\epsilon$? Which of the following statements is true? (A) Problem A is decidable but B is not (B) Problem A is undecidable but B is decidable (C) Both A and B are decidable (D) Both A and B are undecidable
asked
5 days
ago
in
Theory of Computation
by
!KARAN
Junior
(
887
points)

27
views
+1
vote
0
answers
28
Undecidability with PCP
Where can we apply PCP to check, if the grammar is undecidable? Some examples of such grammars Ambiguous grammar Any other example and how they solved with PCP?
asked
6 days
ago
in
Theory of Computation
by
srestha
Veteran
(
103k
points)

32
views
theoryofcomputation
decidability
0
votes
0
answers
29
Extended transition function doubt
α (q1,aba) is {q0, q2} null reachable states are {q0, q1, q2} α (q3,bab) is {q0, q1, q2, q3} none what is extended transition function? and how to solve this kind of question?
asked
6 days
ago
in
Theory of Computation
by
aditi19
Active
(
2k
points)

24
views
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
30
regular expressions
Consider the following statements, which comprises the equality between some regular expressions: S1: ε. ф*= ε. ф+ S2: ф. ф* = ф .ф+ Select the correct option. Both S1 and S2 are correct. Both S1 and S2 are false. 3.S1 is false while S2 is correct. S1 is correct while S2 is fals
asked
6 days
ago
in
Theory of Computation
by
Satbir
Active
(
1.1k
points)

43
views
regularexpressions
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
Ankit Garg 2
jatin khachane 1
Lakshman Patel RJIT
Gupta731
Nilabja Sarkar
Recent Posts
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
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
There is one more problem. Ppl who have...
CL013924707IN rt?
I ordered the GO BOOK 6 dec ....but still i didnt...
thankyou sir
44,160
questions
49,644
answers
163,348
comments
65,809
users