Regular Expression

Question

L = {w|(|#0(w) – #1(w)|mod3) = 1}  is L regular?

Comments

is the answer regular?

Answer 1

Yes.... it is...

Comments

Cool, How did you derive this NFA? It would take lots of time if I were to construct NFA. Is there any faster way to do this?

---

understand like this, suppose k=(#a - #b)  every forward edge i.e. for a is giving 1 + to k nd every reverse edge i.e. fo b giving 1 - "decrement" to k have 3 possible values that is 0,1,2
bcoz of mod 3..

---

Since this involves a mod operation, the result would be any of 0,1,2 or 3 which is finite and we also know that any thing finite can be represented by a DFA. Is my thought process correct?

---

you can't draw NFA/DFA for current language as its not regular ..

look at your NFA , its accepting many strings that are not part of language as 11 ,1011,00 and so many

have a look here

http://www.ugrad.cs.ubc.ca/~cs421/hw/2/a.pdf

Answer 2

1)Mod functions are always Regular .

2)If some language contain relation b/w 'a mod x' and 'b mod y ' then our DFA contains x*y states.

Sorry above DFA is wrong one

The correct DFA for {( #0(w) – #1(w) )mod3) = 1}

and in parallel both my first and second statement are false , good that misconception cleared.

if our question contains {w|(|#0(w) – #1(w)|mod3) = 1} i just notice the actual question is that actually.

Its not regular.

http://www.ugrad.cs.ubc.ca/~cs421/hw/2/a.pdf

tell me if here also some problem.

Comments

you need 1 more final state which is 0,2 
because if #a = 6 and #b = 5  then its difference will be end up going on state 0,2

I found out all final state pairs as 1,0   and  0,2 and 2,1 
Please check
 

---

@aekhn : Thanks aekhn for the attention. that was wrong DFA , sorry for that. i updated the answer , tell me if there also some problem.. i didn't delete wrong DFA as its important to know where do me mistake .