Construct an NFA over alphabet {, } that accepts all words with more a’s modulo 4 than b’s modulo 3.

Question

Construct an NFA over alphabet {, } that accepts all words with more a’s modulo 4 than b’s modulo 3. For example, “” is accepted as it has two a’s and one b. The word “” is accepted as it has six a’s and four b’s.

I must be missing something obvious, as any solution I come up with gets increasingly messy.

I would love to hear anyone else's solutions.

Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community, Jun 24 '23 at 14:53

score 0 · Accepted Answer · answered Jun 24 '23 at 15:07

0

So I build an automata which end states accepted are colored in red and to avoid confusion, I pointed the initial state; here is the link for the quiver diagram

I forgot to color $(2,2)$ in red! and the above $b$ is in fact an $a$

Here is a screenshot of the diagram:

answered Jun 24 '23 at 15:07

julio_es_sui_glace

3,279

well damn, that's 100 times better than what I was doing haha. Thanks for the help! – FunkyFlame Jun 24 '23 at 15:27
You can accept the answer or upvote it if you think you can have better (but it seems it is the simplest possible) – julio_es_sui_glace Jun 24 '23 at 15:28

Construct an NFA over alphabet {, } that accepts all words with more a’s modulo 4 than b’s modulo 3.

1 Answers1