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
Recent questions tagged finiteautomata
Some useful problems
0
votes
0
answers
1
Doubt
The result of cross product of two DFAs is intersection of two languages or union of the two languages?
asked
4 days
ago
in
Theory of Computation
by
aditi19
Junior
(
701
points)

17
views
finiteautomata
0
votes
1
answer
2
Theory of computation
asked
6 days
ago
in
Theory of Computation
by
Mudita
(
41
points)

41
views
theoryofcomputation
finiteautomata
0
votes
0
answers
3
Doubt in Automata
If two finite state machines M and N are isomorphic then M can be transformed to N by relabeling (a) the states alone (b) the edges alone (c) both the states and edges (d) none of the above
asked
Sep 16
in
Theory of Computation
by
goluabhinan
(
77
points)

8
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
0
answers
4
conversion of right linear grammar to DFA
asked
Sep 16
in
Theory of Computation
by
sushmita
Boss
(
13.9k
points)

18
views
theoryofcomputation
finiteautomata
regulargrammar
nfa
0
votes
0
answers
5
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
in
Theory of Computation
by
vaibhav singh 3
(
55
points)

22
views
theoryofcomputation
peterlinz
regularexpressions
finiteautomata
regularlanguages
+2
votes
2
answers
6
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
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

54
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
identifyclasslanguage
+3
votes
1
answer
7
#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
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
12.6k
points)

72
views
theoryofcomputation
finiteautomata
0
votes
1
answer
8
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
in
Theory of Computation
by
goluabhinan
(
77
points)

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

43
views
finiteautomata
theoryofcomputation
minimalstateautomata
0
votes
1
answer
10
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
in
Theory of Computation
by
aambazinga
Junior
(
985
points)

29
views
theoryofcomputation
decidability
finiteautomata
0
votes
2
answers
11
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
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

54
views
finiteautomata
theoryofcomputation
0
votes
0
answers
12
Intro to Automata theory by Ullman Exercise 2nd
asked
Sep 3
in
Theory of Computation
by
Phantom5
(
53
points)

24
views
theoryofcomputation
finiteautomata
0
votes
1
answer
13
Regular Language
Ans. 48
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

59
views
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
1
answer
14
Regular Expression
Ans. D
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

58
views
theoryofcomputation
regularexpressions
finiteautomata
0
votes
2
answers
15
Automata to Regular Expression
Ans. C
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

40
views
finiteautomata
regularexpressions
theoryofcomputation
expression
+1
vote
0
answers
16
Regular expression
Ans. B
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

38
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
0
votes
0
answers
17
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
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

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

60
views
finiteautomata
theoryofcomputation
regularexpressions
0
votes
1
answer
19
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
in
Theory of Computation
by
Things To Know (Thin
(
395
points)

35
views
theoryofcomputation
finiteautomata
regularexpressions
+1
vote
0
answers
20
Minimum number of States
Ans. 5
asked
Aug 30
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

49
views
minimalstateautomata
finiteautomata
theoryofcomputation
numberofstates
0
votes
3
answers
21
DoubtDFA
what is the grammar generated by the complement of this DFA and what is the type?
asked
Aug 29
in
Theory of Computation
by
aditi19
Junior
(
701
points)

24
views
finiteautomata
#dfa
0
votes
1
answer
22
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
in
Theory of Computation
by
dan31
(
27
points)

38
views
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
23
Regular Language
asked
Aug 12
in
Theory of Computation
by
jatinkumar
(
219
points)

69
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
0
votes
0
answers
24
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
in
Theory of Computation
by
manisha11
Junior
(
845
points)

25
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
2
answers
25
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
in
Theory of Computation
by
manisha11
Junior
(
845
points)

37
views
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
1
answer
26
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
in
Theory of Computation
by
Sid865
(
61
points)

45
views
theoryofcomputation
selfdoubt
finiteautomata
0
votes
2
answers
27
Regular expression
Is a*b* + b*a* = ( a + b)* ______
asked
Jul 31
in
Theory of Computation
by
Ajaaz
(
21
points)

100
views
theoryofcomputation
regularexpressions
finiteautomata
nfa
0
votes
3
answers
28
Theory of Computation
Can someone please help me understand these two points about minimum DFA and Minimum NFA, thank you
asked
Jul 31
in
Theory of Computation
by
Ajaaz
(
21
points)

42
views
nfa
#dfa
finiteautomata
theoryofcomputation
minimum
numberofdfa
0
votes
1
answer
29
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
in
Theory of Computation
by
Vikas Verma
Active
(
1.4k
points)

49
views
theoryofcomputation
turingmachine
finiteautomata
Page:
1
2
3
4
5
6
...
18
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
Read/Unread questions
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
following link is Kvs_Pgt_Question Paper...
@Arjun sir how to remove such post? should i hide...
[email protected]
.Plz do share @Sanjay sharma
Please post it as question
This is blog area post it as question
39,825
questions
46,802
answers
140,978
comments
58,918
users