0

I was given an exercise to find DFA for base m no divisible by m. I found out how to do this, thanks to this link, but then I wondered how would we approach this exercise if it was to create an NFA and then convert it to DFA using subset construction method.

I understand that we can insert NULL moves at some place, but I am in search of a straight method, where we convert the problem to NFA seeing only the question. We can also construct a regular expression and the create an NFA, but I can't arrive at a regular expression too.

As an example, for creating NFA for numbers given in base 4 that are divisible by 5.

Nisha
  • 397
  • 1
  • 5
  • 16
  • Can you clarify why you want to first create an NFA and then convert it into a DFA? Is your question how to design an NFA for this problem? Recall that all DFAs are also NFAs. – roctothorpe Sep 25 '18 at 04:33
  • @roctothorpe I wasn't given any such question, I just wondered how would be able to do so! Yes DFAs are also NFAs but I want an NFA which is not a DFA – Nisha Sep 25 '18 at 04:39
  • I don't know of a generalized way to do this. For some bases/divisors, you might be able to take advantage of some divisibility trick - for example, in base 10, a number is divisible by 4 if the last two digits are divisible by 4 so you could have an NFA with epsilon transitions to all of the 2 digit multiples of 4. A number is divisible by 5 if it ends with a 0 or 5 so you could do something similar and non-deterministically guess when you're at the end of the number. – roctothorpe Sep 27 '18 at 22:12

0 Answers0