Search code examples
regexnfa

convert NFA to regular expression and tell whether it is multiple of 3?

i am doing practice and just want to confirm whether i have correctly made the expression and recognize the expression as a multiple of 3?

enter image description here

is that correct expression and my answer:
 ((aaa)* + (bbb)*) 
 expression shows a string length multiple of 3
Solution

  • Yes, your regular expression is correct, language defined by the NFA in picture either accepts null string ^ or (aaa)+ or (bbb)+. You have covered ^ in * closure.

    If you wants you can make its DFA something like as below:

         __ bbb          __ aaa  
     ||              ||
     ▼|              ▼|
--►((Q0))---aaa---►((Q1))

    Where both Q0 and Q1 are final states (Q0 is start state).

    side note: you can replace edge labels of 'aaa' to 'bbb' and 'bbb' to 'aaa' to get another form of same DFA. Additionally, in standard form of DFA an edge lable can be single language symbol.