1

Let $\Sigma = \{0,1\}$

My interpretation of the regular expression = $\Sigma^*01\cup \Sigma^*11\cup \Sigma^*00$

I've created this finite automata with 3 states which I believe fits the criteria. However Im still not sure if I have made this FA correctly. I've checked online resources, watched videos on FA, but I dont have anyone to validate it. Is this a correct representation of the regular expression?

enter image description here

Dravid
  • 61
  • 1
    Your NFA does not accept the string $11$, which it should. – Sassatelli Giulio Dec 22 '22 at 11:56
  • @SassatelliGiulio Ah $A\rightarrow B$ should be 1, 0. Im such an idiot – Dravid Dec 22 '22 at 11:59
  • With $A\stackrel{1,0}\longrightarrow B$, the NFA accepts $10$, which it shouldn't. – Sassatelli Giulio Dec 22 '22 at 18:03
  • @SassatelliGiulio I've been doing more reading, you are right the whole FA is incorrect. In this specific question, I need a DFA right? (find DFA that accepts strings ending in 10, and finding its converse) Or is it possible to find the converse of a NFA (so far my attempts of doing so have failed) – Dravid Dec 22 '22 at 18:48
  • My understanding is that the minimal DFA for this language has $6$ states (these are the strings that don't end in $10$ and have length at least $2$), so you can't do it with DFAs. I don't know of an easy method to find an NFA of the complement given an NFA for the language, but that doesn't necessarily exclude its existence. – Sassatelli Giulio Dec 22 '22 at 18:53
  • Ah okay.. thanks for everything, guess Ill have to keep looking – Dravid Dec 22 '22 at 18:57
  • @SassatelliGiulio I've solved it! – Dravid Dec 22 '22 at 19:48

1 Answers1

1

First made a transition table and created a DFA that did accept all strings ending with 10, found its converse, which was the final answer

enter image description here

Dravid
  • 61
  • 1
    This does not solve the problem in the body of the question, although it solves the problem in the title. -1 for implying that they were the same. – Sassatelli Giulio Dec 23 '22 at 10:20
  • @SassatelliGiulio The regular expression in the body was my interpretation of the question, which is incorrect. I believe it is $\Sigma^* - \Sigma^*10$, although Im not sure if this is an acceptable way to write it – Dravid Dec 23 '22 at 14:38