The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Ullman (TOC) Edition 3 Exercise 2.3 Question 7 (Page No. 68)
In example $2.13$ we claimed that the $NFA$ $N$ is in state $q_{i},$ for $i=1,2,...n,$ after reading input sequence $w$ if and only if the $i^{th}$ symbol from the end of $w$ is $1.$Prove this claim.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

20
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 2.3.7 Problem 2.3.6 (Page No. 67)
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

14
views
ullman
theoryofcomputation
finiteautomata
#dfa
descriptive
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 2.3 Question 5 (Page No. 67)
In the onlyif portion of Theorem $2.12$ we omitted the proof by induction on $w$ that if $\delta_{D}(q_{0},w)=p$ then $\delta_{N}(q_{0},w)=\{p\}.$ Supply this proof.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

11
views
ullman
theoryofcomputation
finiteautomata
descriptive
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 2.3 Question 4 (Page No. 66  67)
Give nondeterministic finite automata to accept the following languages$.$Try to take advantage of nondeterminism as much as possible$.$ The set of strings over the alphabet $\{0,1,.....,9\}$ such that the final digit has appeared ... a number of positions that is a multiple of $4.$ Note that $0's$ is an allowable multiple of $4.$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

10
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
5
Ullman (TOC) Edition 3 Exercise 2.3 Question 3 (Page No. 66)
Convert the following NFA to a DFA and informally describe the language it accepts.
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

17
views
ullman
theoryofcomputation
finiteautomata
0
votes
1
answer
6
Ullman (TOC) Edition 3 Exercise 2.3 Question 2 (Page No. 66)
Convert to a DFA the following NFA$:$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

22
views
ullman
theoryofcomputation
finiteautomata
0
votes
1
answer
7
Ullman (TOC) Edition 3 Exercise 2.3 Question 1 (Page No. 65)
Convert to a DFA the following NFA$:$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

24
views
ullman
theoryofcomputation
finiteautomata
0
votes
0
answers
8
General Query: Self doubt(Math+Automata)
Can somebody explain What is identity permutation?
asked
Apr 1
in
Combinatory
by
srestha
Veteran
(
111k
points)

23
views
discretemathematics
finiteautomata
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 2.4 Question 10
Show that given a regular language $L$, its minimal dfa is unique within a simple relabeling of the states.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

11
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 2.4 Question 9 (Page No. 69)
Write a Computer program that produces a minimal dfa for any given dfa.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

6
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 2.4 Question 10 (Page No. 69)
Prove the following: If the states $q_a$ and $q_b$ are indistinguishable, and if $q_a$ and $q_c$ are distinguishable, then $q_b$ and $q_c$ must be distinguishable.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 2.4 Question 7 (Page No. 69)
Show that indistinguishability is an equivalence relation but that distinguishability is not.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 2.4 Question 6 (Page No. 69)
Prove or disprove the following conjecture. If $M = (Q,Σ,δ,q_0,F)$ is a minimal dfa for a regular language $L$, then $\widehat{M}= (Q, Σ,δ,q_0,Q – F)$ is a minimal dfa for $\overline{L}$.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 2.4 Question 5 (Page No. 69)
Show that if $L$ is a nonempty language such that any $w$ in $L$ has length at least $n$, then any dfa accepting $L$ must have at least $n + 1$ states.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 2.4 Question 4 (Page No. 69)
Minimize the states in the dfa depicted in the following diagram.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 2.4 Question 2 (Page No. 68)
Find minimal dfa's for the following languages. In each case prove that the result is minimal. (a) $L =$ {$a^n b^m :n≥2,m≥1$}. (b) $L =$ {$a^n b:n ≥0$} $∪$ {$b^n a:n ≥1$} (c) $L =$ {$a^n :n ≥ 0,n ≠ 3$}. (d) $L =$ {$a^n:n ≠ 2$ and $n ≠4$}. (e) $L =$ {$a^n:n$ mod $3 = 0$} $∪$ {$a^n: n$ mod $5 = 1$}.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 2.4 Question 1 (Page No. 68)
Minimize the number of states in the dfa of following figure:
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

6
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 2.3 Question 14 (Page No. 62)
Let $L$ be any language. Define $even (w)$ as the string obtained by extracting from $w$ the letters in evennumbered positions; that is, if $w = a_1a_2a_3a_4…$, then $even (w)= a_2a_4.…$ Corresponding to this, we can define a language $even (L) =$ {$even (w): w ∈ L$}. Prove that if $L$ is regular, so is $even(L)$.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 2.3 Question 13 (Page No. 62)
Give a simple verbal description of the language accepted by the dfa in following figure. Use this to find another dfa, equivalent to the given one, but with fewer states.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 2.3 Question 12 (Page No. 62)
Show that if $L$ is regular, so is $L^R$.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 2.3 Question 11 (Page No. 62)
Prove that all finite languages are regular.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

4
views
peterlinz
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 2.3 Question 10 (Page No. 62)
Define a dfa with multiple initial states in an analogous way to the corresponding nfa in Exercise 18, Section 2.2. Does there always exist an equivalent dfa with a single initial state?
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

8
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
23
Peter Linz Edition 4 Exercise 2.3 Question 9 (Page No. 62)
Let $L$ be a regular language that does not contain $λ$. Show that there exists an nfa without $λ$ transitions and with a single final state that accepts $L$.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

13
views
peterlinz
theoryofcomputation
finiteautomata
+1
vote
1
answer
24
Peter Linz Edition 4 Exercise 2.3 Question 8 (Page No. 62)
Find an nfa without $λ$transitions and with a single final state that accepts the set {$a$} $∪$ {$b^n : n ≥1$}.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

30
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa’s?
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 2.3 Question 6 (Page No. 62)
Is it true that for every nfa $M = (Q,Σ,δ,q_0,F)$ the complement of $L(M)$ is equal to the set {$w ∈ Σ^*: δ^*(q_0,w) $ $\cap$ $(QF)$ $\neq$ $Ø$}? If so, prove it. If not, give a counterexample.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

7
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 2.3 Question 5 (Page No. 62)
Is it true that for any nfa $M = (Q,Σ,δ,q_0,F)$ the complement of $L(M)$ is equal to the set {$w ∈ Σ^*: δ^*(q_0,w) $ $\cap$ $F= Ø$}? If so, prove it. If not, give a counterexample.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

6
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 2.3 Question 4 (Page No. 62)
Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N=(Q_N,Σ,δ_N,q_0,F_N)$. Then there exists a deterministic finite accepter $M_D=(Q_D,Σ,δ_D,${$q_0$}$,F_D)$ such that $L=L(M_D)$. Prove this Theorem. Show in ... the label of $\delta ^*_D(q_0,w)$ contains $q_f$, then $\delta ^*_N(q_0,w)$ also contains $q_f$.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

2
views
peterlinz
theoryofcomputation
finiteautomata
proof
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 2.3 Question 3 (Page No. 62)
Convert the following nfa into an equivalent dfa.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

9
views
peterlinz
theoryofcomputation
finiteautomata
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 2.3 Question 2 (Page No. 62)
Convert the nfa in following figure, into an equivalent dfa.
asked
Mar 30
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

5
views
peterlinz
theoryofcomputation
finiteautomata
Page:
« prev
1
2
3
4
5
6
7
8
9
...
27
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
IIITH Preparation and interview experience (M.Tech CSE)
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
Ordering is stopped for now. Will resume after a...
what?
how to buy these books sir??? can we buy from...
You all will get the email tonight.
Hi I have made the payment on
June...
49,576
questions
54,182
answers
187,504
comments
71,143
users