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 nfa
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 1 Question 64 (Page No. 92)
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$ Show that if $A$ is nonempty, A contains some string of length at most k. Show, by giving an example, that $\text{part (a)}$ is not necessarily ... $k.$ Come as close to the bound in $(c)$ as you can$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
2
Michael Sipser Edition 3 Exercise 1 Question 60 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
3
Michael Sipser Edition 3 Exercise 1 Question 38 (Page No. 89)
An $\text{allNFA}$ $M$ is a $\text{5tuple}$ $(Q, Σ, δ, q_{0}, F)$ that accepts $x\in\sum^{*}$ if every possible state that $M$ could be in after reading input $x$ is a state from $F.$ Note ... string if some state among these possible states is an accept state$.$ Prove that $\text{allNFAs}$ recognize the class of regular languages$.$
asked
Apr 28
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

28
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
regularlanguages
0
votes
1
answer
4
Michael Sipser Edition 3 Exercise 1 Question 28 (Page No. 88)
Convert the following regular expressions to $NFA's$ using the procedure given in Theorem $1.54.$ In all parts, $Σ = \{a, b\}.$ $a(abb)^{*}\cup b$ $a^{+}\cup (ab)^{+}$ $(a\cup b^{+})a^{+}b^{+}$
asked
Apr 22
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

48
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
5
Michael Sipser Edition 3 Exercise 1 Question 19 (Page No. 86)
Use the procedure described in $\text{Lemma 1.55}$ to convert the following regular expressions to nondeterministic finite automata. $(0\cup 1)^{*}000(0\cup 1)^{*}$ $(((00)^{*}(11))\cup 01)^{*}$ $\phi^{*}$
asked
Apr 22
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

31
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
0
votes
1
answer
6
Michael Sipser Edition 3 Exercise 1 Question 11 (Page No. 85)
Prove that every $\text{NFA}$ can be converted to an equivalent one that has a single accept state.
asked
Apr 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

27
views
michaelsipser
theoryofcomputation
nfa
proof
0
votes
1
answer
7
Michael Sipser Edition 3 Exercise 1 Question 10 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.49}$ to give the state diagrams of $NFA's$ recognizing the star of the languages described in $\text{\{w w contains at least three 1s\}}$ $\text{\{w w contains at least two 0's and at most one 1\}}$ $\text{The empty set}$
asked
Apr 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

37
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 1 Question 9 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.47}$ to give the state diagrams of $\text{NFA's}$ recognizing the concatenation of the languages described in and input alphabet is $\Sigma=\{0,1\}$ L1={w the length of w is at most 5} and L2={w every odd position of w is a 1} L1={w w contains at least three 1s} and L2=The empty set
asked
Apr 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

34
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
1
answer
9
Michael Sipser Edition 3 Exercise 1 Question 8 (Page No. 84)
Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA's}$ ...
asked
Apr 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

44
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
1
answer
10
Michael Sipser Edition 3 Exercise 1 Question 7 (Page No. 84)
Give state diagrams of $\text{NFA's}$ with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\{0,1\}.$ $\text{The language \{w w ends with 00\} with three states}$ ... $\text{The language}$ $\{\epsilon\}$ $\text{with one state}$ $\text{The language 0* with one state}$
asked
Apr 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

43
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 3.2 Question 18 (Page No. 89)
Find nfa's for $L (aØ)$ and $L (Ø^*)$. Is the result consistent with the definition of these languages?
asked
Apr 3
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

4
views
peterlinz
theoryofcomputation
regularlanguages
nfa
0
votes
0
answers
12
Ullman (TOC) Edition 3 Exercise 2.4 Question 1 (Page No. 71  72)
Design NFA's to recognize the following sets of strings. $abc,abd,$ and $aacd.$ Assume the alphabet is $\{a,b,c,d\}$ $0101,101,$ and $011.$ Assume the alphabet is $\{0,1\}$ $ab,bc,$ and $ca.$ Assume the alphabet is $\{a,b,c\}$
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
39.7k
points)

24
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
13
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
(
39.7k
points)

20
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
14
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
(
39.7k
points)

10
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 3.1 Question 26 (Page No. 77)
Find an nfa that accepts the language $L (aa^* (a + b))$.
asked
Apr 2
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

8
views
peterlinz
theoryofcomputation
regularexpressions
nfa
0
votes
0
answers
16
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

11
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
17
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

28
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
18
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

21
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
19
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

34
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
20
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

13
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
21
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

21
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
22
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

20
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
23
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
Mar 22
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
14k
points)

22
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
24
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)

39
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
+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)

66
views
theoryofcomputation
finiteautomata
nfa
nondeterminism
0
votes
0
answers
26
Geekforgeeks full length
Let L = (0+1)*1(0+1)^(n−1) and following statements regrading language L: The language L can be recognised by a nondeterministic automaton with (n+1) states. Deterministic automaton recognises this language must have at least 2^n states. (Assume n≥1). Which of the ...  According to me, L can be written as (0+1)*1(0+1)* which makes option D most suitable.
asked
Jan 22
in
Theory of Computation
by
vinay chauhan
Active
(
1.1k
points)

17
views
nfa
#dfa
theoryofcomputation
0
votes
1
answer
27
Conversion of NFA to DFA
convert the following NFA to DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
3.7k
points)

116
views
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
28
DFA NFA and ambiguity
Why is Regular grammar obtained from DFA always unambiguous? Why Regular grammar obtained from NFA may or may not be ambiguous?
asked
Dec 7, 2018
in
Theory of Computation
by
OneZero
Active
(
2.1k
points)

43
views
theoryofcomputation
nfa
ambiguous
0
votes
0
answers
29
Extended transition function doubt
α (q1,aba) is {q0, q2} null reachable states are {q0, q1, q2} α (q3,bab) is {q0, q1, q2, q3} none what is extended transition function? and how to solve this kind of question?
asked
Dec 6, 2018
in
Theory of Computation
by
aditi19
Active
(
3.7k
points)

54
views
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
30
Finite Automata
When we convert a (minimal) NFA to DFA by subset construction method, is the DFA obtained always a minimal DFA? Please elaborate.
asked
Nov 15, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

67
views
finiteautomata
theoryofcomputation
minimalstateautomata
nfa
Page:
1
2
3
4
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
Follow @csegate
Recent questions tagged nfa
Recent Blog Comments
@Debargh, Yes. 👍
Thanks. Regarding the probability question, was...
Thanks
What were the Eigen values of A apart from 0? I...
49,540
questions
54,099
answers
187,269
comments
71,006
users