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
Recent questions tagged nfa
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 4 Question 23 (Page No. 212)
Say that an $NFA$ is ambiguous if it accepts some string along two different computation branches. Let $AMBIG_{NFA} = \{ \langle N \rangle \mid \text{ N is an ambiguous NFA}\}$. Show that $AMBIG_{NFA}$ is decidable. (Suggestion: One elegant way to solve this problem is to construct a suitable $DFA$ and then run $E_{DFA}$ on it.)
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

1
view
michaelsipser
theoryofcomputation
nfa
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $kPDA$ be a pushdown automaton that has $k$ stacks. Thus a $0PDA$ is an $NFA$ and a $1PDA$ is a conventional $PDA$. You already know that $1PDAs$ are more powerful (recognize a larger class of languages) than ... $3PDAs$ are not more powerful than $2PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

4
views
michaelsipser
theoryofcomputation
pushdownautomata
nfa
descriptive
0
votes
1
answer
3
CMI2019A2
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n1.$ The shortest word not in $L(A)$ has length at least $n.$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

45
views
cmi2019
finiteautomata
nfa
0
votes
1
answer
4
CMI2019B1
Consider an alphabet $\Sigma=\{a,b\}.$ Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$ Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$ Give an example of a word in $L.$ Give an example of a word not in $L.$ Construct an NFA for $L.$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

31
views
cmi2019
regularexpressions
regularlanguages
nfa
0
votes
0
answers
5
Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 6 (Page No. 317)
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an Lattributed SDD on a topdown parsable grammar. Assume that there is a token char representing any ... never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
asked
Sep 6
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

20
views
ullman
compilerdesign
syntaxdirectedtranslation
regularexpressions
nfa
parser
0
votes
0
answers
6
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
Aug 20
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

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

29
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
8
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
Veteran
(
54.8k
points)

30
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
1
answer
9
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
Veteran
(
54.8k
points)

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

72
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
11
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
Veteran
(
54.8k
points)

84
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
0
votes
1
answer
12
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
Veteran
(
54.8k
points)

45
views
michaelsipser
theoryofcomputation
nfa
proof
0
votes
1
answer
13
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
Veteran
(
54.8k
points)

70
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
0
answers
14
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
Veteran
(
54.8k
points)

54
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
1
answer
15
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
Veteran
(
54.8k
points)

79
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
1
answer
16
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
Veteran
(
54.8k
points)

103
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
0
answers
17
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
(
15.2k
points)

6
views
peterlinz
theoryofcomputation
regularlanguages
nfa
0
votes
0
answers
18
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
Veteran
(
54.8k
points)

37
views
ullman
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
19
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
Veteran
(
54.8k
points)

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

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

11
views
peterlinz
theoryofcomputation
regularexpressions
nfa
0
votes
0
answers
22
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
(
15.2k
points)

15
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
0
answers
23
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
(
15.2k
points)

36
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
24
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
(
15.2k
points)

26
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
25
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
(
15.2k
points)

36
views
peterlinz
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
26
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
(
15.2k
points)

17
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
27
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
(
15.2k
points)

25
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
28
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
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
finiteautomata
nfa
+1
vote
1
answer
29
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
(
15.2k
points)

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

46
views
theoryofcomputation
finiteautomata
nondeterminism
nfa
finiteautomata
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged nfa
Recent Blog Comments
It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
50,647
questions
56,466
answers
195,381
comments
100,313
users