Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a $2DFA$ is finite and is just large enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A $2DFA$ accepts its input by entering a special accept state. For example, a $2DFA$ can recognize the language $\{a^{n}b^{n}c^{n}\mid n\geq 0\}$.
1. Let $A_{2DFA} = \{ \langle M, x \rangle \mid \text {M is a 2DFA and M accepts}\: x\}$. Show that $A_{2DFA}$ is decidable.
2. Let $E_{2DFA} = \{\langle M \rangle \mid \text{M is a 2DFA and} \:L(M) = \emptyset\}$. Show that $E_{2DFA}$ is not decidable.
{"ft_lang_label":"__label__en","ft_lang_prob":0.86507326,"math_prob":0.9983134,"size":839,"snap":"2019-51-2020-05","text_gpt3_token_len":259,"char_repetition_ratio":0.10538922,"word_repetition_ratio":0.0,"special_character_ratio":0.29797378,"punctuation_ratio":0.0882353,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992127,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-12-16T12:49:51Z\",\"WARC-Record-ID\":\"<urn:uuid:ceafcf57-610e-4f96-ac99-890caf45850d>\",\"Content-Length\":\"65622\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:01d4729a-dff8-4831-b00c-5df342e1f0bf>\",\"WARC-Concurrent-To\":\"<urn:uuid:5d81f4de-ab34-413c-adb4-5d416151de9c>\",\"WARC-IP-Address\":\"104.27.188.78\",\"WARC-Target-URI\":\"https://gateoverflow.in/324073/michael-sipser-edition-3-exercise-5-question-26-page-no-240\",\"WARC-Payload-Digest\":\"sha1:QXMFPXODNPCFJAJSA7ZOVCD6BI3ZZPMN\",\"WARC-Block-Digest\":\"sha1:4BVYGVGUFW2XS3PXRKLHPGPSSDWGOIHD\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-51/CC-MAIN-2019-51_segments_1575540565544.86_warc_CC-MAIN-20191216121204-20191216145204-00284.warc.gz\"}"}