Register

Michael Sipser Edition 3 Exercise 4 Question 23 (Page No. 212)

359 views
0 votes
0 votes
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.)
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
admin asked Oct 17, 2019
233 views
Michael Sipser Edition 3 Exercise 4 Question 27 (Page No. 212)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
0 votes
1 answer
2
admin asked Oct 17, 2019
320 views
Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 votes
0 votes
0 answers
3
admin asked Oct 17, 2019
236 views
Michael Sipser Edition 3 Exercise 4 Question 25 (Page No. 212)
Let $BAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some string containing an equal number of 0s and 1s}\}$. Show that $BAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
Let $BAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some string containing an equal number of 0s and 1s}\}$.Show that $BAL_{DFA}$ is decidable. (Hin...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 17, 2019
257 views
Michael Sipser Edition 3 Exercise 4 Question 17 (Page No. 212)
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
User Avatar
Link Copied!