edited by
231 views

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Oct 17, 2019
228 views
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...
0 votes
0 votes
1 answer
2
admin asked Oct 17, 2019
312 views
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...
0 votes
0 votes
0 answers
4
admin asked Oct 17, 2019
250 views
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.