1
$\begingroup$

Question Background

A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):

Definition of Finite Automaton

The image below (taken from the Wikipedia article on combinational logic) seems to suggest that combinational logics can be used to define formal grammars that describe formal languages just the same as regular expressions/FSMs, pushdown automatons, and turing machines.

Automata Theory

The Question

Is this, in fact, the case? And if so, what is the formal definition of a combinational logic? Is it a finite automata/5-tuple that has a transition function that always specifies a transition to it's one and only state (since it is time-indepedent)? NOTE: I consider it inappropriate to couple boolean logic and digital circuitry to a mathematical model which should strive for maximal generalization

References

Sipser, Introduction to the Theory of Computation, (2nd Edition). Thompson Course Technology, 2006.

Improve this question
$\endgroup$
3
  • $\begingroup$ Automaton with a single state. Able to transform an input symbol to an output symbol. $\endgroup$
    – greybeard
    Jan 18 at 8:52
  • $\begingroup$ I was leaning towards a definition like that. Do we have an official source though? $\endgroup$
    – Shadow43375
    Jan 18 at 10:25
  • $\begingroup$ Indeed! My opinion is that "combinational logic" should be removed from the diagram in wikipedia. Instead as a part of automata theory it is part of complexity theory, as witnessed elsewhere: en.wikipedia.org/wiki/Complexity_class#Boolean_circuits $\endgroup$
    – Hendrik Jan
    Jan 18 at 14:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.