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 nfadfa
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

3
views
michaelsipser
theoryofcomputation
nfadfa
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

6
views
michaelsipser
theoryofcomputation
pushdownautomata
nfadfa
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, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

64
views
cmi2019
finiteautomata
nfadfa
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, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

48
views
cmi2019
regularexpressions
regularlanguages
nfadfa
+1
vote
1
answer
5
CMI2018B1
Consider the following nondeterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
asked
Sep 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

41
views
cmi2018
finiteautomata
nfadfa
descriptive
0
votes
0
answers
6
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, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59k
points)

30
views
ullman
compilerdesign
syntaxdirectedtranslation
regularexpressions
nfadfa
parser
0
votes
0
answers
7
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, 2019
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
59k
points)

2
views
ullman
compilerdesign
nfadfa
grammar
lr0item
descriptive
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{www\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
asked
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

22
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 1 Question 65 (Page No. 93)
Prove that for each $n > 0,$ a language $B_{n}$ exists where $B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, and if $B_{n} = A_{1}\cup...\cup A_{k},$ for regular languages $A_{i},$ then at least one of the $A_{i}$ requires a $\text{DFA}$ with exponentially many states$.$
asked
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

13
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
10
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

31
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
1
answer
11
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

33
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
1
answer
12
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

43
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
regularlanguages
0
votes
1
answer
13
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

79
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
0
votes
1
answer
14
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

96
views
michaelsipser
theoryofcomputation
regularexpressions
nfadfa
0
votes
1
answer
15
Michael Sipser Edition 3 Exercise 1 Question 17 (Page No. 86)
Give an $NFA$ recognizing the language $(01 ∪ 001 ∪ 010)^{*}.$ Convert this $NFA$ to an equivalent $DFA.$ Give only the portion of the $DFA$ that is reachable from the start state.
asked
Apr 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

61
views
michaelsipser
theoryofcomputation
nfadfa
0
votes
1
answer
16
Michael Sipser Edition 3 Exercise 1 Question 16 (Page No. 86)
Use the construction given in $\text{Theorem 1.39}$ to convert the following two nondeterministic finite automata to equivalent deterministic finite automata.
asked
Apr 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

80
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 1 Question 14 (Page No. 85)
Show that if $M$ is a $DFA$ that recognizes language $B,$ swapping the accept and not accept states in $M$ yields a new $DFA$ recognizing the complement of $B.$ Conclude that the class of regular languages is closed under ... of $C.$ Is the class of languages recognized by $NFA's$ closed under complement$?$ Explain your answer$.$
asked
Apr 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

33
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 1 Question 13 (Page No. 85)
Let $F$ be the language of all strings over $\{0,1\}$ that do not contain a pair of $1's$ that are separated by an odd number of symbols. Give the state diagram of a $\text{DFA}$ with five states that recognizes $F.$ $($You may find it helpful first to find a $4$state $\text{NFA}$ for the complement of $F.)$
asked
Apr 21, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

100
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
0
votes
1
answer
19
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

51
views
michaelsipser
theoryofcomputation
nfadfa
proof
0
votes
1
answer
20
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

77
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
statediagram
0
votes
0
answers
21
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

62
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
statediagram
0
votes
1
answer
22
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

92
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
statediagram
descriptive
0
votes
1
answer
23
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

114
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
statediagram
descriptive
0
votes
0
answers
24
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, 2019
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.4k
points)

7
views
peterlinz
theoryofcomputation
regularlanguages
nfadfa
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 2.5 Question 2 (Page No. 79)
Consider the following $\inNFA.$ Compute the $\in$closure of each state. Give all the strings of length three or less accepted by the automaton. Convert the automaton to a DFA.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

11
views
ullman
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 2.5 Question 1 (Page No. 79)
Consider the following $\inNFA.$ Compute the $\in$closure of each state. Give all the strings of length three or less accepted by the automaton. Convert the automaton to a DFA.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

15
views
ullman
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 2.4 Question 2 (Page No. 72)
Design NFA's to recognize the following sets of strings. $abc,abd,$ and $aacd.$ Asssume the alphabet is $\{a,b,c,d\}$ $0101,101,$ and $011.$ Asssume the alphabet is $\{0,1\}$ $ab,bc,$ and $ca.$ Asssume the alphabet is $\{a,b,c\}$ Convert each of your NFA's to DFA's.
asked
Apr 3, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

41
views
ullman
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
28
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

42
views
ullman
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
29
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

27
views
ullman
theoryofcomputation
finiteautomata
nfadfa
0
votes
0
answers
30
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59k
points)

21
views
ullman
theoryofcomputation
finiteautomata
nfadfa
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged nfadfa
Recent Blog Comments
While raising objections what works as...
It is mentioned "Left for Evaluation" so no...
I think this discussion will keep on going till...
do we have to include marks of qs that are left...
@roh6jmon yes, it is there.
50,737
questions
57,317
answers
198,368
comments
105,103
users