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 Edition 4 Exercise 2.3 Question 1 (Page No. 62)
Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N= (Q_N, Σ,δ N,q0,F_N)$. Then there exists a deterministic finite accepter $M_D= (Q_D, Σ,δ_D,${$q_0$}$,F_D)$ such that $L= L (M_D)$. convert the nfa in following figure to a dfa: Can you see a simpler answer more directly?
asked
21 hours
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 2.2 Question 21 (Page No. 56)
An nfa in which (a) there are no λtransitions, and (b) for all $q ∈ Q$ and all $a ∈ Σ$, $δ (q,a)$contains at most one element, is sometimes called an incomplete dfa. This is reasonable since the conditions make it such that there is never any choice of moves. For $Σ = $ {$a,b$}, convert the incomplete dfa below into a standard dfa
asked
21 hours
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
3
Peter Linz Edition 4 Exercise 2.2 Question 20 (Page No. 56)
Show that for any nfa for all $q ∈Q$ and all $w, v ∈ Σ^*$ : $\delta ^*(q,wv)=\cup _{p\epsilon \delta ^*(q,w)}\delta ^*(p,v)$ [Use Definition: For an nfa, the extended transition function is defined so that $δ^* (q_i,w)$ ... walk in the transition graph from $q_i$ to $q_j$ labeled $w$. This holds for all $q_i, q_j ∈ Q$, and $w ∈ Σ^*$.]
asked
21 hours
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 2.2 Question 18 (Page No. 55)
An nfa with multiple initial states is defined by the quintuple $M =(Q, Σ,δ,q0,F)$, where $Q_0 ⊆ Q$ is a set of possible initial states. The language accepted by such an automaton is defined as $L (M)=$ ... the same language. Also, Suppose that we made the restriction $Q_0 ∩ F= Ø$. Would this affect the conclusion? (Question 19)
asked
22 hours
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
5
Peter Linz Edition 4 Exercise 2.2 Question 16 (Page No. 55)
Find an nfa that accepts {$a$}* and is such that if in its transition graph a single edge is removed (without any other changes), the resulting automaton accepts {$a$}. Can this be solved using a dfa? If so, give the solution; if not, give convincing arguments for your conclusion. (Question 17)
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

6
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 2.2 Question 14 (Page No. 55)
Let $L$ be the language accepted by the nfa in the following figure: Find an nfa that accepts $L$ $∪$ {$a^5$} .
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 2.2 Question 13 (Page No. 55)
What is the complement of the language accepted by the nfa in the following figure:
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 2.2 Question 11 (Page No. 55)
Find an nfa with four states for $L$ = {$a^n: n ≥ 0$} $∪$ {$b^na: n ≥ 1$} .
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 2.2 Question 8 (Page No. 55)
Construct an nfa with three states that accepts the language {$ab,abc$}*.
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

1
view
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 2.2 Question 7 (Page No. 55)
Design an nfa with no more than five states for the set {$abab^n: n ≥ 0$} $∪$ {$aba^n: n ≥ 0$}. Do you think this can be solved with fewer than three states? (Question 9)
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 2.2 Question 6 (Page No. 55)
For the nfa in following figure, find $δ^*(q_0, 1010)$ and $δ^* (q_1,00)$
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

3
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 2.2 Question 5 (Page No. 55)
In following figure, find $δ^* (q_0, a)$ and $δ^* ( q_1,λ)$
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 2.2 Question 4 (Page No. 55)
In following figure, find $δ^* (q_0,1011)$ and $δ^* (q_1,01)$
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 2.2 Question 3 (Page No. 55)
Find a dfa that accepts the complement of the language defined by the nfa in figure:
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 2.2 Question 2 (Page No. 55)
Find a dfa that accepts the language defined by the nfa in figure:
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
1
answer
16
Peter Linz Edition 4 Exercise 2.1 Question 25 (Page No. 49)
While the language accepted by a given dfa is unique, there are normally many dfa's that accept a language. Find a dfa with exactly six states that accepts the same language as the dfa in figure:
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 2.1 Question 23 (Page No. 49)
Let $G_M$ be the transition graph for some dfa $M$. Prove the following: (a) If $L (M)$ is infinite, then $G_M$ must have at least one cycle for which there is a path from the initial vertex to some vertex in the cycle and a path from some vertex in the cycle to some final vertex. (b) If $L (M)$ is finite, then no such cycle exists.
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

3
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 2.1 Question 22 (Page No. 49)
Let, $L$= {$awa: w ∈ $ {$a,b$}* }. Show that $L$* is regular.
asked
1 day
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
1
answer
19
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

15
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
20
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

12
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
21
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

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

11
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
23
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
24
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
1
answer
25
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
+1
vote
1
answer
26
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

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

9
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
2
answers
28
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
29
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
3 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

5
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
0
answers
30
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
4 days
ago
in
Theory of Computation
by
Naveen Kumar 3
Loyal
(
6.2k
points)

6
views
theoryofcomputation
peterlinz
finiteautomata
Page:
1
2
3
4
5
6
...
23
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
Important Dates for Counselling (GATE 2019)
IIT Gandhinagar review
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
75
Is doing ME in CS and SS from Bits Pilani...
can anybody compare it with other new iits such...
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
48,720
questions
52,807
answers
183,452
comments
68,470
users