The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook 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
Recent questions tagged finiteautomata
Some useful problems
0
votes
0
answers
1
Peter linz
From a language L we create a new language chop2 (L)by removing the two leftmost symbols of every string in L. Specifically, chop2(L) = {w: vw ∈ L, with v= 2}. Show that if L is regular, then chop2 (L) is also regular.
asked
Sep 14, 2018
in
Theory of Computation
by
vaibhav singh 3
(
135
points)

58
views
theoryofcomputation
peterlinz
regularexpressions
finiteautomata
regularlanguages
+2
votes
2
answers
2
Regular Language
Is the given Grammer represent a regular language ? S>AaB A>aC  epsilon B>aB  bB  epsilon C>aCb  epsilon
asked
Sep 13, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

107
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
identifyclasslanguage
+3
votes
2
answers
3
#tocself doubt
Which of the following below are regular? (1)$\{wxw^r  w \in (0,1)^+,x\in(0,1)^*\}$ (2)$\{wxw^r  w \in (0,1)^*,x\in(0,1)^+\}$ (3)$\{ww^rx\, w\in (0,1)^*,x \in (0,1)^+\}$ (4)$\{ww^rx w\in (0,1)^+, x\in (0,1)^*)\}$
asked
Sep 12, 2018
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
24.4k
points)

122
views
theoryofcomputation
finiteautomata
0
votes
1
answer
4
Doubt in regular expressions
Consider the regular expression R = a*b* + b*a*. The number of equivalence classes of Σ* to represent a language which is equivalent to R is ____________.
asked
Sep 12, 2018
in
Theory of Computation
by
goluabhinan
(
101
points)

88
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
0
votes
1
answer
5
Doubt in Finite Automata
Consider the following DFA D. The number of states in the minimization of D is __________.
asked
Sep 12, 2018
in
Theory of Computation
by
goluabhinan
(
101
points)

60
views
finiteautomata
theoryofcomputation
minimalstateautomata
0
votes
1
answer
6
TOC DECIDABILITY
Let E={<M> M is a DFA that accepts some strings with more 1's than 0's} Show that E is decidable. How can E be decidable. How can a DFA compare between number of 1's and 0's. From the question I know that it's not talking about all, but some. The things is even some should not be decidable. isn't it?
asked
Sep 8, 2018
in
Theory of Computation
by
aambazinga
Active
(
3.2k
points)

52
views
theoryofcomputation
decidability
finiteautomata
0
votes
2
answers
7
Finite automata
The number of DFA with four states that can be constructed over alphabet {a,b} with designated initial state are 2^n then value of n is .....
asked
Sep 5, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

71
views
finiteautomata
theoryofcomputation
0
votes
0
answers
8
Intro to Automata theory by Ullman Exercise 2nd
Exercise 2.2.8: Let A be a DFA and a particular input symbol of A, such that for all states q of A we have delta(q,a) = q. A) Show that for all n >= 0, Delta cap(q, a^n) = q. where a^n is the string consisting of n a's. note delta = δ and delta cap = δˆ.
asked
Sep 3, 2018
in
Theory of Computation
by
Phantom5
(
63
points)

57
views
theoryofcomputation
finiteautomata
0
votes
1
answer
9
Regular Language
Ans. 48
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

79
views
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
1
answer
10
Regular Expression
Ans. D
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

111
views
theoryofcomputation
regularexpressions
finiteautomata
0
votes
2
answers
11
Automata to Regular Expression
Ans. C
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

79
views
finiteautomata
regularexpressions
theoryofcomputation
expression
+1
vote
0
answers
12
Regular expression
Ans. B
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

60
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
0
votes
0
answers
13
Finite Automata
Ans.D My approach: Since it doesn't say about wether its NFA or DFA i considered it as NFA ,so i can create a initial state where there is a self loop on both 0 and 1 and other transition defined for other non final state so obviously for any string ... string i would still be in the initial state which is the final state so i can accept any subset of Sigma* Is my approach valid ?
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

41
views
finiteautomata
nfa
0
votes
2
answers
14
TOC Finite Automata
How to construct a finite automata equivalent to the regular expression: ( 0 + 1 )* ( 00 + 11 ) ( 0 + 1 )*
asked
Sep 1, 2018
in
Theory of Computation
by
iarnav
Loyal
(
9.5k
points)

323
views
finiteautomata
theoryofcomputation
regularexpressions
0
votes
1
answer
15
Theory of computation
Which of the following CFG’s can’t be simulated by an FSM ? a. S>Sa/b b. S>aSb/ab c. S>abX, X>cY, Y>d/aX d. None of these
asked
Aug 31, 2018
in
Theory of Computation
by
Rackson
Active
(
1.8k
points)

57
views
theoryofcomputation
finiteautomata
regularexpressions
+1
vote
0
answers
16
Minimum number of States
Ans. 5
asked
Aug 30, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

75
views
minimalstateautomata
finiteautomata
theoryofcomputation
numberofstates
0
votes
3
answers
17
DoubtDFA
what is the grammar generated by the complement of this DFA and what is the type?
asked
Aug 29, 2018
in
Theory of Computation
by
aditi19
Active
(
2.3k
points)

37
views
finiteautomata
#dfa
0
votes
1
answer
18
Finite State Automata
Every DFA is NFA but not vice versa Can you please explain how this statement is true? Reference: https://www.geeksforgeeks.org/tocfiniteautomataintroduction/
asked
Aug 28, 2018
in
Theory of Computation
by
dan31
Junior
(
657
points)

50
views
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
19
Regular Language
asked
Aug 12, 2018
in
Theory of Computation
by
jatinkumar
(
265
points)

83
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
0
votes
0
answers
20
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, 2018
in
Theory of Computation
by
manisha11
Active
(
1.9k
points)

39
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
2
answers
21
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, 2018
in
Theory of Computation
by
manisha11
Active
(
1.9k
points)

54
views
theoryofcomputation
regularlanguages
finiteautomata
+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, 2018
in
Theory of Computation
by
Sid865
(
61
points)

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

128
views
theoryofcomputation
regularexpressions
finiteautomata
nfa
0
votes
3
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, 2018
in
Theory of Computation
by
Ajaaz
(
39
points)

55
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, 2018
in
Theory of Computation
by
Vikas Verma
Active
(
3.4k
points)

65
views
theoryofcomputation
turingmachine
finiteautomata
0
votes
1
answer
26
theory of computation
check whether given language is regular or not 1) (an) n where n ≥1 2) ( am ) n where n ≥ 1 3) w= { (( a 2 ) n) * (( an )2 )* } where n ≥ 1
asked
Jul 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

120
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
0
votes
2
answers
27
theory of computation
{ W X Wr  w,x ∈ (a+b)+ } this language is regular....how?
asked
Jul 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

86
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
+1
vote
0
answers
28
self doubt
is it necessary for the gate exam that minimisation of dfa can be solved by partitiong method ?? will it be safe to escape partitining method and problem can be solved by table filling method??
asked
Jul 18, 2018
in
Theory of Computation
by
vijju532
Active
(
1.1k
points)

47
views
theoryofcomputation
finiteautomata
nfa
0
votes
2
answers
29
Doubt Regular Language and regular expressions
Is it safe to say (ab*)* = (a+b)*  {b}? or any string will be missed apart from b
asked
Jul 16, 2018
in
Theory of Computation
by
abhiram144
(
137
points)

113
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
Page:
« prev
1
2
3
4
5
6
7
8
9
...
21
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
Gate contest link is now open
Official keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Relax... But....
Barc : Arjun Sir
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
Is there any option that the answer can be 3 or 4?
Yes.
Yes sir, and if we solve, it'll be 4.00
Well in the link if you see GB is 1000*1000*1000...
47,913
questions
52,296
answers
182,255
comments
67,746
users