The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
44 views

asked ago in Theory of Computation by (219 points) | 44 views
+1

I am giving you the transition table. Drawing DFA will be too unclear to understand.

The states are written in the form of Q(na%3)(nb%3).

Q00 is the initial state. On getting 1 a we go to Q10. Here the subscript has importance. It counts the mod value of a and b. When we give 1 a then na%3=1 and nb%3=0.

Taking another example : Q20 is a state where na%3=2 and nb%3=0. On getting another a it goes to Q00 because now the no. of a's has increased by 1 and na%3=0.

The states Qab with b>=a are the final states.

  a b
->*Q00 Q10 Q01
Q10 Q20 Q11
*Q01 Q11 Q02
Q20 Q00 Q21
*Q11 Q21 Q12
*Q02 Q12 Q00
Q21 Q01 Q22
*Q12 Q22 Q10
*Q22 Q02 Q20

Hopefully this table is okay..

1 Answer

+1 vote
Best answer

If you make the final state to non final and non final states to final then it becomes FA of n(a) mod3>n(b) mod3. :)

answered ago by Junior (505 points)
selected ago by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,053 questions
45,544 answers
131,860 comments
48,884 users