edited by
163 views

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Oct 17, 2019
179 views
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
0 votes
0 votes
0 answers
2
admin asked Oct 17, 2019
142 views
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
0 votes
0 votes
0 answers
3
admin asked Oct 15, 2019
190 views
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
0 votes
0 votes
0 answers
4
admin asked Oct 15, 2019
210 views
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.