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.
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
0
votes
1
answer
1
Language Regular or not
Is it regular? $\left \{ \left ( 0^{n} \right )^{m}n<m,n,m\geq 1 \right \}$
asked
2 days
ago
in
Theory of Computation
by
srestha
Veteran
(
84.2k
points)

89
views
theoryofcomputation
regularlanguages
identifyclasslanguage
+1
vote
2
answers
2
Gradup topicwise question doubt
Identify the language generated by the following grammar: S>AB A>aAb€ where € read as epsilon B>bBb (A){a^m b^nn≥m, m>0} (B){a^m b^nn≥m, m≥0} (C){a^m b^nn>m, m>0} (D){a^m b^nn>m, m≥0} I select option C but it is wrong, correct answer is option D. I could not understand Gradup answer explanation.Please help me to rectify my fault.
asked
2 days
ago
in
Theory of Computation
by
Sona Barman
Active
(
1.1k
points)

28
views
theoryofcomputation
language
of
grammar
0
votes
2
answers
3
Doubt .... Theory of Computation ..... Regular Expression
asked
5 days
ago
in
Theory of Computation
by
abhiram144
(
25
points)

51
views
theoryofcomputation
regularexpressions
0
votes
1
answer
4
Doubt ..... Theory of Computing
find regular expression over $\{a,b\}$ corresponding to "set of strings containing Exactly $2a's$.". I have come up with two answers and are seeming Logically correct to me. Please correct me If I am wrong. 1. $b^* a b^* a b^*$  This ... $b$ In the middle of $2 a's$ and $2 a's$ at the end. I am wondering if both of them are correct. Thanks in advance.
asked
5 days
ago
in
Theory of Computation
by
abhiram144
(
25
points)

41
views
theoryofcomputation
regularexpressions
0
votes
1
answer
5
Regular expression#previous year gate
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ number of $1's$ and preceded by at least $k$ number of $1's$ ($k$ is a fixed integer).Choose the correct one out of two. $1^*1^k(01^k)^*1^*$ $1^*(1^k01^k)^*$
asked
5 days
ago
in
Theory of Computation
by
MeghnaJain
(
7
points)

71
views
theoryofcomputation
regularexpressions
0
votes
1
answer
6
PDA for a language
$a^i b^j / i$ should not be equal to $2j+1$ give PDA for this language
asked
May 17
in
Theory of Computation
by
sanju77767
(
151
points)

45
views
theoryofcomputation
pushdownautomata
0
votes
0
answers
7
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)

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

48
views
finiteautomata
theoryofcomputation
regularexpressions
dfa
nfa
0
votes
2
answers
9
Theory of computation doubt
Cfl is closed under intersection with regular language. Then resultant languages will be regular or cfl ? Let X is cfl Y is regular language L=X intersection Y Then L is what?
asked
May 10
in
Theory of Computation
by
Dhoomketu
(
129
points)

50
views
theoryofcomputation
closure
properties
0
votes
1
answer
10
what the language accebted by
asked
May 9
in
Theory of Computation
by
doaa
(
31
points)

36
views
theoryofcomputation
0
votes
0
answers
11
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)

72
views
theoryofcomputation
regularexpressions
finiteautomata
+2
votes
2
answers
12
Grade up topicwise questions
L1={a^n b^n c ^mm>=0 and n>=0} L2={a^m b^ n c^ nn>=0 and m>=0} If L3=L1UL2 then how many of L1,L2,L3 are context free languages? A)1 (B)2 (C)3 (D) none Answer given option C. Please explain?
asked
May 8
in
Theory of Computation
by
Sona Barman
Active
(
1.1k
points)

66
views
theoryofcomputation
contextfreelanguage
0
votes
2
answers
13
No of states in Minimal DFA
Ques: Let ∑= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8)? *[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].
asked
May 8
in
Theory of Computation
by
kislaya Pant
(
41
points)

66
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
+1
vote
1
answer
14
Minimal Final States in DFA
Ques: What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4).
asked
May 8
in
Theory of Computation
by
kislaya Pant
(
41
points)

53
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
1
answer
15
Test Series
If there are Q states in NFA, DFA should have at max $2^{Q}$ states. Keeping this thing in mind I answered the question but it went wrong. Please if anyone can give the correct solution.
asked
May 6
in
Theory of Computation
by
Subham Nagar
Junior
(
507
points)

67
views
testseries
finiteautomata
theoryofcomputation
0
votes
2
answers
16
Context Free Language
L= { $a^{n}b^{m}$  $n<=m<=2n$ } a) DCFL b) CFL but not DCFL c) Not CFL
asked
May 6
in
Theory of Computation
by
Subham Nagar
Junior
(
507
points)

79
views
contextfreelanguage
theoryofcomputation
grammar
0
votes
1
answer
17
TheGateAcademy Test Series
In DFA, does each state need to have transition on "EACH" input alphabet? The answer was given "False" but I dont think so. Can anyone explain? Because if this statement is False, then there is no use of "Dead State"
asked
May 6
in
Theory of Computation
by
Subham Nagar
Junior
(
507
points)

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

32
views
theoryofcomputation
0
votes
1
answer
19
Automata (How to create DFA for the language)
asked
May 6
in
Theory of Computation
by
kislaya Pant
(
41
points)

49
views
theoryofcomputation
minimalstateautomata
finiteautomata
+1
vote
1
answer
20
peter linz
given regular language L = {$a^n$b:n≥0} $L^2$  L = $L^2$ since there's no string in $L^2$ which is in L. Am i correct ?
asked
May 5
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.6k
points)

61
views
theoryofcomputation
peterlinz
regularlanguages
0
votes
1
answer
21
Peter Linz Chapter 4.3 Exercise Q.20
I don't think it will be regular . Had the language been uwwRv the expression could have been (a+b)*(aa+bb)(a+b)* as there is no restriction on w. Is it correct? and if it isn't regular, is it a CFL?
asked
May 4
in
Theory of Computation
by
Subham Nagar
Junior
(
507
points)

61
views
theoryofcomputation
regularlanguages
regularexpressions
0
votes
1
answer
22
Peter Linz Chapter 4
L = {a^n: n ≥ 2, is a prime number}. This is not a regular language. What about L*? Is it regular? Please explain.
asked
May 4
in
Theory of Computation
by
Subham Nagar
Junior
(
507
points)

48
views
theoryofcomputation
regularexpressions
regularlanguages
+1
vote
0
answers
23
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)

57
views
theoryofcomputation
peterlinz
dfa
+3
votes
1
answer
24
give cfg for the language
Let $L=\{w \mid w \in (0+1)^+ , N_0(w) \le N_1(w) \le 2N_0(w) \}$,where $N_i(w)$ represents number of $i's$ in string $w$. a) Give a CFG for $L$ b) is Lc = Σ* L context  free? c) Let $\frac{1}{2}$L = $\{x  ∃y ∈ L , x = y , x.y ∈ L \}$.is $\frac{1}{2}$L contextfree?
asked
Apr 30
in
Theory of Computation
by
Sambit Kumar
Active
(
3.6k
points)

173
views
cfg
theoryofcomputation
0
votes
1
answer
25
Theory of computetion
Suppose we have a FA N(a)mod3=0 In this FA the initial state and final state is same If we will reverse this FA the state will be remain same or not that initial state and final state is going to be the same or not and after reversing the string the strings are not getting reverse it will accept only $L=\{\epsilon,b,bb,bbbb,bbb,bbbbbb.............\}$ plzz rectify my doubt
asked
Apr 29
in
Theory of Computation
by
sanju77767
(
151
points)

47
views
theoryofcomputation
0
votes
0
answers
26
#Peter Linz #8.9
In Theorem 8.1, find a bound for $m$ in terms of the properties of the grammar $G$.
asked
Apr 28
in
Theory of Computation
by
pallaviamu
(
113
points)

19
views
theoryofcomputation
0
votes
1
answer
27
self doubt
What is the differene between { Φ } and λ and what happens when we concatenate this with a regular language ??
asked
Apr 25
in
Theory of Computation
by
ankit aingh
(
103
points)

42
views
theoryofcomputation
regulargrammar
0
votes
1
answer
28
TOC Decidability Theory
Which of the following problems is solvable? a) Writing a universal Turing machine b) Determining if an arbitrary Turing machine is a Universal Turing Machine c) Determining if a universal Turing Machine can be written in fewer than k instructions for some k d) Determining if a universal Turing Machine and some input will halt
asked
Apr 25
in
Theory of Computation
by
gauravkc
Loyal
(
5.4k
points)

134
views
decidability
theoryofcomputation
turingmachine
0
votes
1
answer
29
pushdownautomata
asked
Apr 23
in
Theory of Computation
by
sumitr
(
17
points)

29
views
theoryofcomputation
pushdownautomata
dpda
selfdoubt
+2
votes
2
answers
30
ISRO201826
The $FSM$ (Finite State Machine) machine pictured in the figure above Complements a given bit pattern Finds $2's$ complement of a given bit pattern Increments a given bit pattern by $1$ Changes the sign bit
asked
Apr 22
in
Theory of Computation
by
Arjun
Veteran
(
342k
points)

783
views
isro2018
finiteautomata
theoryofcomputation
mooremealymachine
Page:
1
2
3
4
5
6
...
77
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
IISC CSA shortlist to final select conversion
career advice
IIT Madras MS written test and interview
Interview experience at IIITSricity
IIT Delhi Interview Experience  M.tech. Computer Technology  22 May 2018
Follow @csegate
Gatecse
Recent questions tagged theoryofcomputation
Recent Blog Comments
Hi Rishabh, when you solved the previous year ...
@Ajit I am seriously noone to suggest anything to ...
@VS You had a rank of 1800, hence you did have a ...
Applied Online.The notification came in March ...
Online. The notification came in March 2018
35,519
questions
42,843
answers
121,778
comments
42,191
users