Finite accepter(machine Design)

Question

What is product automata and what is the difference between grid machine and mod machine?

Comments

whats the topic i can't get it!

---

The topic is minimal FA design or simply designing dfa or nfa machine for regular languages

---

grid machine and mod machine?

from where u got this word will send me the links

---

I don't have any book link.I saw these terms when I was doing a design problem of modular operations like (w|w mod x =n).

Your solution tells me the application of these kind of machine.Please can you exactly tell me more about these machines.

---

(w|w mod x =n).

w%x= n

means w is the length of some string when u applied mod operation here it will be n i think this kind of automata will

be design by using turing machine

i think

---

No it will be a regular machine because we are not counting the length of string.We are asking the remainder or residue of the string when it is divided by a certain number and since the modular operations are cyclic in nature the residue of mod n will not go beyond n-1hence the states are finite(using myhil nerode theorem it can be easily proved) hence the machine will be a finite acceptor. What my doubt is I want to know is the difference between a mod machine and a grid machine.

Answer 1

product automata: this is from compound aurtomata

example of finite automata accept odd no. of a's and even no. of b's(  * indicate final state)

QUE:(q0,q1*)belongs to FA of odd no of a's AND(q2,q3*)belongs to FA of even no. b's

AND:(q0,q1*) * (q2,q3*)=(q0q2,q1q2,q0q3,q1*q3*)

QUE:(q0,q1*)belongs to FA of odd no of a's OR(q2,q3*)belongs to FA of even no. b's

OR:(q0,q1*) * (q2,q3*)=(q0q2,q1q2*,q0q3*,q1q3*)

Answer 2

I think the size of grid machine = (m+1)(n+1) and size of the modMachine = m*n