Register

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

• retagged by
324 views

1 Answer

0 votes
0 votes
Its is decidable because the language is Context Free and is accepted by a PDA.
User Avatar
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
239 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
0 answers
2
admin asked Oct 17, 2019
237 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
262 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!