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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 8 (Page No. 259)
We suggested that individual items could be regarded as states of a nondeterministic finite automaton, while sets of valid items are the states of a deterministic finite automaton (see the box on "Items as States of an NFA" ... the NFA that comes from the valid items for a grammar produces the $LR(0)$ sets of items.
asked
3 days
ago
in
Compiler Design
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

1
view
ullman
compilerdesign
nfa
grammar
lr0item
descriptive
0
votes
0
answers
2
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
(
45.8k
points)

13
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
3
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
(
45.8k
points)

25
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
4
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
(
45.8k
points)

36
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
regularlanguages
0
votes
1
answer
5
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
(
45.8k
points)

54
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
6
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
(
45.8k
points)

53
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
0
votes
1
answer
7
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
(
45.8k
points)

30
views
michaelsipser
theoryofcomputation
nfa
proof
0
votes
1
answer
8
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
(
45.8k
points)

46
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
0
answers
9
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
(
45.8k
points)

40
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
1
answer
10
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
(
45.8k
points)

55
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
1
answer
11
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
(
45.8k
points)

66
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
0
answers
12
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)

5
views
peterlinz
theoryofcomputation
regularlanguages
nfa
0
votes
0
answers
13
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
(
45.8k
points)

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

23
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
15
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
(
45.8k
points)

11
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
16
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)

9
views
peterlinz
theoryofcomputation
regularexpressions
nfa
0
votes
0
answers
17
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)

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

30
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
19
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)

22
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
20
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
21
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)

14
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
22
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)

24
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
23
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)

22
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
24
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)

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

41
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
+1
vote
1
answer
26
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)

67
views
theoryofcomputation
finiteautomata
nfa
nondeterminism
0
votes
0
answers
27
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
28
Conversion of NFA to DFA
convert the following NFA to DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
4k
points)

124
views
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
29
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)

45
views
theoryofcomputation
nfa
ambiguous
0
votes
0
answers
30
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
(
4k
points)

67
views
theoryofcomputation
finiteautomata
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged nfa
Recent Blog Comments
Thanks a lot
Please tell me when will the books be back in...
Congrats you deserved it. Best of Luck.
Sorry, that was missed. You'll get it today.
49,839
questions
54,799
answers
189,490
comments
80,677
users