# Converting NFA to DFA

I've converted an NFA to a DFA. But even after checking over it a few times, it still doesn't feel right. I'm sure this is trivial, but I'd like someone to give me an idea where I went totally wrong on this.

NFA: DFA: • Why would you say it doesn't feel right? It does to me. – Untitled Sep 20 '13 at 3:01
• You could use ony drawing tool to get nicer images (Libre Office Draw, GraphViz, LaTeX with TikZ, ...). At least you can crop and rotate the images properly, convert to grayscale and fiddle around with contrast and brightness. As for your question, there are algorithms to do this conversion; why do you doubt them? – Raphael Sep 20 '13 at 15:20

Well, of course you have to merge the two empty states and there should be two transitions $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ if you want a complete automaton, but otherwise, it looks right and I agree with Subhayan: both automata accept $ab^+ \cup ab^+a$.
• I added $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ so it just merges with the $\emptyset$ closest to it. So there's still two $\emptyset$ on the graph. How wrong is that? It's really for convenience when drawing. – stackuser Sep 20 '13 at 15:54
Based on your constructions, it seems like both machines accept the same language, i.e. $ab^+ \cup ab^+a$.
• i tried to "simulate the machines" independently, it seemed to me that the DFA and NFA both accepted languages that start with $a$, contains at-least one $b$ and also those (with the same conditions as prev and) that end with an $a$. Do you think I got it wrong somehow? – Subhayan Sep 20 '13 at 4:59
{"ft_lang_label":"__label__en","ft_lang_prob":0.9583463,"math_prob":0.8689154,"size":1012,"snap":"2020-24-2020-29","text_gpt3_token_len":265,"char_repetition_ratio":0.0734127,"word_repetition_ratio":0.43820226,"special_character_ratio":0.25296444,"punctuation_ratio":0.14351852,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96102923,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,3,null,3,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-16T14:17:49Z\",\"WARC-Record-ID\":\"<urn:uuid:ba5af8c7-aa2d-42f2-a35e-76cf72f82d35>\",\"Content-Length\":\"157544\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8b848c62-a4e0-4863-ae36-ac622b582793>\",\"WARC-Concurrent-To\":\"<urn:uuid:f9cfd496-6a75-451e-adeb-6f3f505af4bf>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/14458/converting-nfa-to-dfa\",\"WARC-Payload-Digest\":\"sha1:UYFZMNS6RLMHH5ATTGD3NMGG3L75DI2V\",\"WARC-Block-Digest\":\"sha1:77YN4FEOSSL6B7IRSIGPTKEYOHTOXGNK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593657169226.65_warc_CC-MAIN-20200716122414-20200716152414-00371.warc.gz\"}"}