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
Lists
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
Does ambiguity problem is decidable for regular grammar(right linear grammar)?
asked
9 hours
ago
in
Theory of Computation
by
sandyoverflow
(
17
points)

10
views
theoryofcomputation
finiteautomata
0
votes
0
answers
2
Pushdown Automata
asked
1 day
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

38
views
pushdownautomata
theoryofcomputation
dpda
0
votes
0
answers
3
Context Free Grammar
Consider the following CFG 'G' S> aA/bSS/SS A> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked
2 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

17
views
theoryofcomputation
contextfreegrammars
contextfreelanguage
cfg
pushdownautomata
0
votes
0
answers
4
Finite Automata
asked
2 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

19
views
finiteautomata
theoryofcomputation
minimalstateautomata
regularexpressions
0
votes
1
answer
5
Theory of Computation
$L1= \left \{ a^m b^n c^n d^m  m \neq n \right \}$ $L2= \left \{a^i b^j c^k  (i<=j)or (j<=i), j=k \right \}$ $L3= \left \{a^i b^j c^k i=j, j<k \right \}$ The number of the above languages that are context free are ?
asked
2 days
ago
in
Theory of Computation
by
Priyam Pandey
(
61
points)

69
views
contextfreelanguage
theoryofcomputation
0
votes
2
answers
6
TOC Regular Langauges
Is L= 0n1 n>=0 regular? Is the kleene closure i.e. (L)* regular?
asked
2 days
ago
in
Theory of Computation
by
sakharam
Active
(
2.3k
points)

104
views
regularlanguages
theoryofcomputation
finiteautomata
0
votes
0
answers
7
Dfa for no states
What is the difference between a dfa accepting epsilon moves and dfa accepting nothing? I have a dfa which has no states what will be the dfa this is regarding,this question https://gateoverflow.in/8362/gate2015152
asked
3 days
ago
in
Theory of Computation
by
sripo
(
293
points)

12
views
minimalstateautomata
theoryofcomputation
finiteautomata
numberofstates
theoryofcomputation_
0
votes
0
answers
8
GO Classroom(TOC)
What is Squareroot(L) and Square(L)?
asked
3 days
ago
in
Theory of Computation
by
sakharam
Active
(
2.3k
points)

32
views
theoryofcomputation
goclassroom
0
votes
0
answers
9
self doubt
does DPDA have epsilon transition ??
asked
4 days
ago
in
Theory of Computation
by
vijju532
(
469
points)

14
views
theoryofcomputation
0
votes
0
answers
10
Made Easy
asked
4 days
ago
in
Theory of Computation
by
Asutosh
(
389
points)

15
views
madeeasytestseries
theoryofcomputation
cfg
0
votes
0
answers
11
DECIDABILITY
L = {<M>  L(M) = {1}} L = {<M>  L(M) is {} } L = {<M>  L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
asked
4 days
ago
in
Theory of Computation
by
Smishra95
Active
(
1.3k
points)

18
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
0
votes
0
answers
12
Construct DFA for given Language
For the language which ends with 01 or 11 or 10 or 11 for $\sum$={0,1}* .Is dfa possible for this language?
asked
4 days
ago
in
Theory of Computation
by
sripo
(
293
points)

14
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
0
votes
0
answers
13
To test if the given language is regular.
asked
4 days
ago
in
Theory of Computation
by
sripo
(
293
points)

43
views
regularexpressions
regularlanguages
finiteautomata
theoryofcomputation
gate2019preparation
0
votes
0
answers
14
Can a^p where p is a prime number be an NFA?
asked
4 days
ago
in
Theory of Computation
by
sripo
(
293
points)

33
views
theoryofcomputation
finiteautomata
nfa
#dfa
regularlanguages
regularexpressions
0
votes
0
answers
15
TOC Self Doubt
If L1 is CFL and L2 is Regular L. $L1\cap L2 = L3$ Then L3 is CFL. Can L3 be regular also sometimes and if L3 is CFL and Regular also does it employs L1 is also Regular ??
asked
6 days
ago
in
Theory of Computation
by
jatin khachane 1
Junior
(
805
points)

30
views
theoryofcomputation
regularlanguages
identifyclasslanguage
0
votes
0
answers
16
Regular Languages
Which is the equivalent Regular Expression for the following: "Strings in which every group of 3 symbols should contain atleast 1 a." a)[(a+b) (a+b)a]* b) [(a+b) (a+b)a]* [(a+b)(a+b)a]* c)[(ϵ + b + bb)a]* [ ϵ+ b + bb] d) (abb)* (bab)b* (bba)*
asked
6 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

21
views
theoryofcomputation
regularlanguages
regularexpressions
finiteautomata
0
votes
0
answers
17
Formal Languages
Let r1 = (b*ab*ab*ab*)* and r2= (b*ab*ab*)*. What is L(r1) ∩ L(r2)? a) L[b*ab*ab*ab*)*] b) L[b*ab*ab*)*] c) L[b*ab*ab*)6] d) L[b*ab*ab*ab*ab*ab*ab*)*]
asked
6 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

24
views
theoryofcomputation
grammar
regularlanguages
0
votes
0
answers
18
Formal Languages
Let r1= (a+b2)* , r2 = (a* + b*)* , r3 = (a2 + b)* Which of the following is true? a)L(r1) is a subset of L(r2) and L(r3) is a subset of L(r2) b)L(r2) is a subset of L(r1) and L(r2) is a subset of L(r3) c)L(r1) = L(r3) is a subset of L(r2) d) L(r1) U L(r3) = L(r2)
asked
6 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

18
views
theoryofcomputation
grammar
regularlanguages
0
votes
1
answer
19
Formal Languages
If G= ({S} , {a}, {S>SS} , S), then language L(G) is a)ϕ b)aa(a)* c)(aa)* d)None of these
asked
6 days
ago
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
761
points)

19
views
theoryofcomputation
finiteautomata
grammar
0
votes
0
answers
20
TOC SELF DOUBT
L = { w ∈ {a,b}* : a(w) = b(w) } We're using the notation: a(w) = number of a's in a string w b(w) = number of b's in a string w S⇾ aSbS  bSaS  ε Doubt: Is the same language generated by below grammar also: S⇾ SS  aSb  bSa  ε
asked
6 days
ago
in
Theory of Computation
by
jatin khachane 1
Junior
(
805
points)

29
views
theoryofcomputation
contextfreegrammars
0
votes
0
answers
21
Concatenation of DCFLs
L1={an bn  n>=0} L2={bn cn  n>=0} What is L1.L2 ? Is it an b2n cn ?
asked
Oct 13
in
Theory of Computation
by
sripo
(
293
points)

19
views
theoryofcomputation
dcfl
contextfreelanguages
identifyclasslanguage
0
votes
0
answers
22
Grammar to DFA Construction
For the given Grammar S>aAbB A>bCaS B>aCbS C>aBbA Construct DFA I am getting confused in understanding how to take the final state.
asked
Oct 13
in
Theory of Computation
by
sripo
(
293
points)

25
views
theoryofcomputation
finiteautomata
regulargrammar
numberofdfa
minimalstateautomata
+1
vote
0
answers
23
Subset of a regular language
Let L be a regular language over {a,b}, Suppose a new language defined as follows, L = x1 , x2, x3, x4,........ L1 = x5, x10, x15 ..... L1 is defined as taking every string which is at positon 5, 10, 15 and so on, in other words, the positions that can be divided by 5. Is L1 regular?
asked
Oct 13
in
Theory of Computation
by
AnilGoudar
Active
(
4.6k
points)

14
views
theoryofcomputation
regularlanguages
discretemathematics
finiteautomata
0
votes
0
answers
24
pushdownauto
Consider the below mentioned PDA M1 (Q, ∑, Г, δ, q0, Z, F) which accepts thelanguage L. Where: Q={q0, q1, q2, q3, q4} Σ={a,b} Г={a,b,Z} Z=initial pushdown symbol F=set of final states, empty in this case as the string is accepted by null store. Choose the correct Grammar ... . 1. S → aaBbaab, B → aaBbaab 2. None of the above. 3. S →aaBb∊, B →aaBbaab 4. S →aaBbaab∊, B →aaBbaab
asked
Oct 13
in
Theory of Computation
by
Bhupendra
(
279
points)

9
views
theoryofcomputation
0
votes
0
answers
25
dfa and nfa
Let M1 be a NFA with “k1” states and the corresponding DFA of M1 have “k2”states. Then which of the following option is necessarily false in every case. 1.k2 = k1 2.k2 ≤2k1 3.k2<k1 4. None of the above
asked
Oct 13
in
Theory of Computation
by
Bhupendra
(
279
points)

12
views
theoryofcomputation
0
votes
0
answers
26
Turing Machine
A turing machine $\left \langle M,w,i \right \rangle$ where $M$ is TM , $w$ is string and $i$ is bit. Is the bit $i$ is encoding at last of the string $w$ or at first?
asked
Oct 12
in
Theory of Computation
by
srestha
Veteran
(
98.5k
points)

17
views
turingmachine
theoryofcomputation
0
votes
0
answers
27
Fermat Little Theorem(Ullman)
int exp(int i,int n){ int ans,j; ans=1; for(j=1;j<=n;j++){ ans*=i; return ans; } } main(){ int n,total,x,y,z; scanf("%d",&n); total=3; while(1){ for(x=1(;x<=total2;x++){ for(j=1;j<=totalx1;j++){ z=totalxy; if(exp(x,n)+exp(y,n)==exp(z,n)) printf("Hello World"); } total++; } } } What the following code print?
asked
Oct 12
in
Theory of Computation
by
srestha
Veteran
(
98.5k
points)

19
views
theoryofcomputation
0
votes
0
answers
28
TOC : Minimum State in Finite Automata ( virtualgate )
asked
Oct 12
in
Theory of Computation
by
arya_stark
(
447
points)

16
views
theoryofcomputation
finiteautomata
minimalstateautomata
numberofstates
0
votes
0
answers
29
toc q
L={a$^{n}$$b^{^{n}}$ n>=0 and n $\neq$10} lang is
asked
Oct 11
in
Theory of Computation
by
amit166
(
233
points)

34
views
theoryofcomputation
0
votes
1
answer
30
Gateforum Test Series
What is Turing Decidable and Turing Recognizable and What to conclude from those terms?
asked
Oct 10
in
Theory of Computation
by
Gupta731
(
297
points)

36
views
gateforumtestseries
theoryofcomputation
Page:
1
2
3
4
5
6
...
87
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
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Daily Quiz
Follow @csegate
Gatecse
Recent questions tagged theoryofcomputation
Recent Blog Comments
Nice 2 know. You are welcome. :)
Hello @Arjun, I got books now...thanks for your...
You may contact FedEx local delivery office. It...
Yes you are right, it's showing this status from...
FedEx delivery is shown and as per that it is out...
40,976
questions
47,609
answers
146,779
comments
62,342
users