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
1
answer
1
Peter Linz Edition 4 Exercise 2.1 Question 20 (Page No. 48)
Let $L$ be the language accepted by the automaton in the following figure. Find a DFA that accepts $L^2$.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

15
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
2
Peter Linz Edition 4 Exercise 2.1 Question 19 (Page No. 48)
Show that $δ^*(q,wv)=δ^*(δ^*(q,w),v)$ for all $w,v ∈ Σ^*$ . (symbols have standard meaning)
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

12
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
3
Peter Linz Edition 4 Exercise 2.1 Question 18 (Page No. 48)
Show that if $L$ is regular, so is $L$ $∪$ {$a$}, for all $a∈Σ$.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
+1
vote
2
answers
4
Peter Linz Edition 4 Exercise 2.1 Question 17 (Page No. 48)
Show that if $L$ is regular, so is $L $ {$λ$} .
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

11
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 2.1 Question 16 (Page No. 48)
Show that the set of all real numbers in $C$ is a regular language.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 2.1 Question 15 (Page No. 48)
Show that the language $L =$ {$a^n: n$ is a multiple of $3$, but not a multiple of $5$} is regular.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
1
answer
7
Peter Linz Edition 4 Exercise 2.1 Question 14 (Page No. 48)
Show that the language L= {$a^n: n$ is either a multiple of $3$ or a multiple of $5$} is regular.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
1
answer
8
Peter Linz Edition 4 Exercise 2.1 Question 13 (Page No. 48)
Show that the language $L= $ {$a^n: n ≥ 0,n ≠ 4$} is regular.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
1
answer
9
Peter Linz Edition 4 Exercise 2.1 Question 12 (Page No. 48)
Show that $L=$ {$a^n: n ≥4$} is regular.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

9
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
2
answers
10
Peter Linz Edition 4 Exercise 2.1 Question 11 (Page No. 48)
Show that the language $L=$ {$vwv: v, w ∈$ {$a,b$}*$, v= 2$} is regular.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 2.1 Question 10 (Page No. 48)
Construct a dfa that accepts strings on {$0,1$} if and only if the value of the string, interpreted as a binary representation of an integer, is zero modulo five. For example, $0101$ and $1111$, representing the integers $5$ and $15$, respectively, are to be accepted.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

5
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 2.1 Question 8 (Page No. 47)
A run in a string is a substring of length at least two, as long as possible and consisting entirely of the same symbol. For instance, the string $abbbaab$ contains a run of $b$'s of length three and a run of $a$'s of length two. Find dfa's ... length either two or three}. (d) $L$= {$w$ : there are exactly two runs of $a$'s of length 3}.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

6
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 2.1 Question 6 (Page No. 47)
With $Σ = $ {$a,b$} , give a dfa for $L =$ {$w_1aw_2: w1≥ 3, w2≤ 5$}.
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

7
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 2.1 Question 5 (Page No. 47)
Give dfa's for the languages (a) $L$= {$ab^5wb^2 : w ∈ $ {$a,b$}* } , (b) $L$= {$ab^na^m : n ≥ 2 , m ≥3$ } , (c) $L$ = {$w_1abw_2 : w_1 ∈$ {$a,b$}*,$w_2 ∈$ {$a,b$}* } .
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
1
answer
15
Peter Linz Edition 4 Exercise 2.1 Question 3 (Page No. 47)
$L$ = {$awa : w ∈$ {$a,b$}* } Show that if we change the following figure, making $q_3$ a nonfinal state and making $q_0, q_1,q_2$ final states, the resulting dfa accepts $\bar{L}$
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
1
answer
16
Peter Linz Edition 4 Exercise 2.1 Question 2 (Page No. 47)
For $Σ$= {$a,b$}, onstruct dfa's that accept the sets consisting of (a) all strings with exactly one $a$, (b) all strings with at least one $a$, (c) all strings with no more than three $a$'s
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
1
answer
17
Peter Linz Edition 4 Exercise 2.1 Question 1 (Page No. 47)
Which of the strings 0001, 01001, 0000110 are accepted by the dfa
asked
2 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

6
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 1.2 Question 7 (Page No. 28)
Are there languages for which $(L^c)^*=(L^*)^c$
asked
4 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.1k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
19
#TOC What will be the minimal DFA of this regular language?
Given L = { 0*1 + 0 + 1* + 10*1} where + symbol is UNION and NOT positive closure. Please draw the Minimal DFA for this.
asked
Mar 14
in
Theory of Computation
by
iarnav
Loyal
(
9.6k
points)

51
views
finiteautomata
regularexpressions
regs
theoryofcomputation
pumpinglemma
0
votes
0
answers
20
#TOC what is the minimum pumping length of this regular language?
asked
Mar 11
in
Theory of Computation
by
iarnav
Loyal
(
9.6k
points)

65
views
pumpinglemma
theoryofcomputation
finiteautomata
0
votes
0
answers
21
Ullman 2nd edition Theorem 2.22 (Section 2.5)
Here why they are saying we must convert DFA transition into NFA transition?
asked
Mar 3
in
Theory of Computation
by
Bhaskar Singh
(
257
points)

37
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
0
votes
1
answer
22
Peter Linz Edition 4 Exercise 3.1 Question 5 (Page No. 75)
what is the regular grammar for L={$a^nb^m$  n+m is even}
asked
Feb 24
in
Theory of Computation
by
aditi19
Active
(
2.4k
points)

154
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
regularexpressions
regulargrammar
+1
vote
0
answers
23
Peter Linz Edition 4 Exercise 3.3 Question 6 (Page No. 97)
Construct a right linear grammar for the language L(aab*ab)* is this grammar correct? S>aaA  ε A>bA  abA  S
asked
Feb 24
in
Theory of Computation
by
aditi19
Active
(
2.4k
points)

43
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
regulargrammar
+1
vote
1
answer
24
Peter Linz Edition 4 Exercise 3.2 Question 10.b (Page No. 88)
What is the regular expression for this
asked
Feb 22
in
Theory of Computation
by
aditi19
Active
(
2.4k
points)

143
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
regularexpressions
+1
vote
1
answer
25
Self Doubt  Confusion on language represented by DFA and NFA
If a DFA "D" have symbol {0,1,2} and NFA "N" have symbol {0,1} but both are representing strings ending with 01 and whole string only contain {0,1} then can we say L(N) = L(D) i.e language represented by DFA is equal to language represented by NFA?
asked
Feb 20
in
Theory of Computation
by
Bhaskar Singh
(
257
points)

57
views
theoryofcomputation
finiteautomata
nfa
nondeterminism
0
votes
1
answer
26
Peter Linz Edition 4 Exercise 2.1 Question 9.a (Page No. 48)
Construct a DFA on {0, 1} where every 00 is followed immediately by 1
asked
Feb 19
in
Theory of Computation
by
aditi19
Active
(
2.4k
points)

102
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
0
votes
1
answer
27
MadeEasy WorkBook: Thoery of Computation  Finite Automata
asked
Feb 16
in
Theory of Computation
by
Jyoti Kumari97
(
225
points)

72
views
madeeasybooklet
theoryofcomputation
finiteautomata
0
votes
3
answers
28
GATE201948
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identify function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
386k
points)

2.4k
views
gate2019
numericalanswers
theoryofcomputation
finiteautomata
0
votes
1
answer
29
#TOC #Examples
Give examples of: Countable Infinite Set Countable Finite Set Uncountable Finite Set Uncountable Infinite Set
asked
Jan 31
in
Theory of Computation
by
Reshu $ingh
(
345
points)

58
views
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
30
#TOC #PumpingLemma
What is Pumping length? Why we consider pumping length of certain numbers? Can Pumping length be 0?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
345
points)

44
views
theoryofcomputation
finiteautomata
Page:
1
2
3
4
5
6
...
22
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
IIT Gandhinagar review
Is DAIICT good for doing MTech ?
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
One word would be "Priorities" Second word shall...
What's interesting to me is that despite having...
Brother!! your all posts are really worth to read...
48,634
questions
52,769
answers
183,405
comments
68,307
users